1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TF(i, p, q) for(int i = (p); i <= (q); ++i)
#define TR(i, q, p) for(int i = (q); i >= (p); --i)
#define V vector
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define th third
#define rz resize
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define sz(V) (int)(V.size())
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b);
typedef pair<int,int> ii;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<vector<int>>vvi;
typedef vector<vector<bool>>vvb;
typedef vector<bool> vb;
typedef vector<ii> vii;
constexpr int inf = 1e18 + 9;
int n, m;
int step;
int realstep;
int nstp(int& TS, vi& ml, V<multiset<ii>>& bv, vvi& upst){
    ++realstep; ++step; step %= m;
    if(!step){
        ii x = *bv[m-1].rbegin();
        TS += x.fi; int id = x.se;
        TF(i, 0, m-1){
            bv[i].erase({upst[id][i], id});
            cmin(ml[i], upst[id][m-1] - upst[id][i]);
        }
        return TS;
    }
    else{
        int ts = TS;
        int opt1 = bv[m-1].rbegin()->fi - ml[step-1];
        int opt2 = bv[step-1].rbegin()->fi;
        return (ts + max(opt1, opt2));
    }
}
void solve(){
    int k; cin >> n >> m >> k;
    vvi upst;
    vi dws;
    vi ups;
    TF(i, 1, n){
        bool ups = false;
        vi ct;
        TF(j, 1, m){
            int a; cin >> a;
            ct.pb(a);
            if(j > 1){
                if(ct[j-1] != ct[j-2]){
                    ups = ct[j-1] > ct[j-2];
                }
            }
        }
        if(ups) upst.pb(ct);
        else{
            for(int v : ct) dws.pb(v);
        }
    }
    sort(rall(dws));
    V<multiset<ii>>bv(m);
    TF(i, 0, sz(upst)-1){
        bv[0].insert({upst[i][0], i});
        TF(j, 1, m-1){
            upst[i][j] += upst[i][j-1]; 
            bv[j].insert({upst[i][j], i});
        }
    }
    TF(i, 1, sz(dws)-1) dws[i] += dws[i-1];
    int score = 0;
    int TS = 0;
    vi ml(m, inf);
    TR(i, min(k, sz(dws)), 0){
        int idx = min(sz(dws), i);
        int s = 0;
        if(idx) s = dws[idx-1];
        int rest = k-idx;
        if(rest > n*m-sz(dws)) break;
        while(realstep < rest-1){
            nstp(TS, ml, bv, upst);
        }
        int x = 0;
        if(rest) x = nstp(TS, ml, bv, upst);
        s += x;
        cmax(score, s);
    }
    cout << score;
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); solve();
}