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
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct wynik{int p, q; ll s;};

bool operator<(const vector<ll> &a, const vector<ll> &b){
    ll x = 0, y = 0;
    for(auto it:a) x += it;
    for(auto it:b) y += it;
    return x > y;
}

void add(const vector<ll> &V, vector<vector<ll>> &A, vector<ll> &B, vector<ll> &S){
    for(int i=1; i<V.size(); i++){
        if(V[i-1] > V[i]){
            for(auto it:V) B.push_back(it);
            return;
        }
    }

    A.push_back(V);
    ll s = 0;
    for(auto it:V) s += it;
    S.push_back(s);
}

wynik sim(const vector<ll> &PB, const vector<ll> &S, int k, int m, int i){
    int p = 0, q = 0, cnt = 0;
    ll s = 0;
    int r = min((int)PB.size()-1, k % m);
    s += PB[r] - PB[q];
    cnt += r - q;
    q = r;
    while(cnt + m <= k){
        int r = min(q+m, (int)PB.size()-1);
        if(p < S.size() && S[p] >= PB[r] - PB[q]){
            s += S[p];
            cnt += m;
            p++;
        }
        else{
            s += PB[r] - PB[q];
            cnt += r - q;
            q = r;
        }
    }
    return {p, q, s};
}

ll res(int p, int q, int i, int j, const vector<ll> &S, const vector<ll> &B, ll s, int m, ll sc){
    if(j < 1) return s;
    if(i < p){
        s -= S[i];
        int r = min(q+m, (int)B.size()-1);
        if(p >= S.size() || S[p] < B[r] - B[q]) s += B[r] - B[q];
        else if(p < S.size()) s += S[p];
    }
    //if(i < 1 && j == 4) cerr << s << " " << w << " " << sc << q << " " << "\n";
    return s + sc;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> A;
    vector<ll> B, S;
    for(int i=0; i<n; i++){
        vector<ll> V(m);
        for(auto &it:V) cin >> it;
        add(V, A, B, S);
    }

    sort(B.begin(), B.end());
    sort(S.begin(), S.end());
    sort(A.begin(), A.end());
    reverse(B.begin(), B.end());
    reverse(S.begin(), S.end());
    vector<ll> PB(B.size()+1);
    PB[0] = 0;
    for(int i=1; i<=B.size(); i++) PB[i] = PB[i-1] + B[i-1];

    // for(int i=0; i<A.size(); i++){
    //     for(auto it:A[i]) cerr << it << " ";
    //     cerr << "\n";
    // }
    // cerr << "\n";
    // for(auto it:S) cerr << it << " ";
    // cerr << "\n";
    // for(auto it:PB) cerr << it << " ";
    // cerr << "\n";
    
    vector<wynik> W(m);
    for(int i=0; i<min(m, k+1); i++) W[i] = sim(PB, S, k-i, m, i);
    //for(auto it:W) cerr << it.p << " " << it.q << " " << it.s << "\n";

    ll w = W[0].s;
    for(int i=0; i<A.size(); i++){
        ll sc = 0;
        for(int j=0; j<min(m, k+1); j++){
            if(j > 0) sc += A[i][j-1];
            ll x = res(W[j].p, W[j].q, i, j, S, PB, W[j].s, m, sc);
            //cerr << i << " " << j << " " << sc << " " << x << "\n";
            w = max(w, x);
        }
    }
    cout << w << "\n";
}