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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, m;
ll k;
ll o;
vector<ll> ph;
vector<ll> typ1;
vector<vector<ll>> typ2;

ll pref1[300'007];
ll suma_stosu[300'007];

int idx[300'007];

ll pref2pelne[300'007];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m >> k;
    
    for (int i=0; i<n; i++) {
        ph.clear();
        for (int j=0; j<m; j++) {
            cin >> o;
            ph.push_back(o);
        }
        
        if (m == 1 || ph[0] >= ph[m-1]) {
            for (ll el : ph) typ1.push_back(el);
        } else {
            typ2.push_back(ph);
        }
    }
    
    sort(typ1.rbegin(), typ1.rend());
    
    for (int i=0; i<typ1.size(); i++) pref1[i+1] = pref1[i]+typ1[i];
    
    int t = typ2.size();
    for (int i=0; i<t; i++) {
        for (int j=0; j<m; j++) {
            suma_stosu[i] += typ2[i][j];
        }
    }
    
    for (int i=0; i<t; i++) idx[i] = i;
    
    sort(idx, idx+t, [](int a, int b) {
        return suma_stosu[a] > suma_stosu[b];
    });
    
    vector<vector<ll>> sortedtyp2(t);
    vector<ll> sortedsum(t);
    
    for (int i=0; i<t; i++) {
        sortedtyp2[i] = typ2[idx[i]];
        sortedsum[i] = suma_stosu[idx[i]];
    }
    
    for (int i=0; i<t; i++) pref2pelne[i+1] = pref2pelne[i]+sortedsum[i];
    
    ll out=0;
    
    // glowna petla
    for (int p=0; p<m; p++) {
        
        vector<ll> min_bot(t);
        vector<ll> max_top(t);
        
        if (p > 0 && t > 0) {
            vector<ll> topP(t);
            vector<ll> botP(t);
            
            for (int i=0; i<t; i++) {
                ll top_sum=0;
                
                for (int j=0; j<p; j++) {
                    top_sum += sortedtyp2[i][j];
                }
                topP[i] = top_sum;
                botP[i] = sortedsum[i]-top_sum;
            }
            
            // mins
            ll curr_min = 2e18;
            for (int i=0; i<t; i++) {
                curr_min = min(curr_min, botP[i]);
                min_bot[i] = curr_min;
            }
            
            // maxs
            ll curr_max = -1;
            for (int i=t-1; i>=0; i--) {
                curr_max = max(curr_max, topP[i]);
                max_top[i] = curr_max;
            }
        }
        
        for (int c=0; c<=t; c++) {
            ll E = (ll)c*m + p;
            
            if (E>k) continue;
            if (k-E > (ll)typ1.size()) continue;
            
            ll zysk2 = 0;
            
            if (p==0) {
                zysk2=pref2pelne[c];
            } else {
                if (c == t) continue;
                
                ll opta=-1, optb=-1;
                
                if (c<t) {
                    opta = pref2pelne[c+1]-min_bot[c];
                }
                
                if (c<t) {
                    optb = pref2pelne[c]+max_top[c];
                }
                
                zysk2 = max(opta,optb);
            }
            
            out = max(out, zysk2+pref1[k-E]);
        }
    }
    
    cout << out << "\n";
    
    return 0;
}