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
#include <bits/stdc++.h>
using namespace std;
using ind = long long;
using cind = const ind;
#define FOR(i,l,r) for(ind i = (l); i <= (r); i++)
#define FORD(i,l,r) for(ind i = (l); i >= (r); i--)
#define DEBUG_ON false
#define debug if constexpr(DEBUG_ON)
#define err debug cerr

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ind N, M, K;
    cin >> N >> M >> K;
    vector<ind> stos;
    vector<vector<ind>> stosy;
    FOR(ni,1,N){
        if(M == 1) {stos.push_back(0); cin >> stos.back(); continue;}
        stosy.push_back({});
        stosy.back().resize(M);
        FOR(mi,1,M) cin >> stosy.back()[mi-1];
        bool is_decreasing=true;
        FOR(mi,1,M-1) if(stosy.back()[mi-1] < stosy.back()[mi]) is_decreasing = false;
        if(is_decreasing){
            for(auto k : stosy.back()) stos.push_back(k);
            stosy.pop_back();
        }
    }
    sort(stos.begin(), stos.end(), [](ind a, ind b){
        return a > b;
    });
    sort(stosy.begin(), stosy.end(), [](const auto& a, const auto& b){
        ind s1 = 0;
        ind s2 = 0;
        for(auto k : a) s1 += k;
        for(auto k : b) s2 += k;
        return s1 > s2;
    });
    if(stosy.size()==0){
        ind s=0;
        FOR(i,0,min(K-1,ind(stos.size())-1)) s += stos[i];
        cout << s << '\n';
        return 0;
    }
    ind stos_sum[300'001];
    if(stos.size()>0) {
        stos_sum[0]=stos[0];
        stos[0]=0;
        FOR(i,1,ind(stos.size())-1) stos_sum[i] = stos_sum[i-1] + stos[i];
        FOR(i,stos.size(),300'000) stos_sum[i] = stos_sum[i-1];
    }else{
        FOR(i,0,300'000) stos_sum[i]=0;
    }
    ind stosy_stos1[300'001];
    ind stosy_stos1_sum[300'001];
    FOR(i,0,300'000) stosy_stos1[i]=0;
    FOR(i,0,300'000) stosy_stos1_sum[i]=0;
    FOR(i,0,ind(stosy.size())-1) for(auto k : stosy[i]) stosy_stos1[i]+=k;
    stosy_stos1_sum[0] = stosy_stos1[0];
    FOR(i,1,300'000) stosy_stos1_sum[i] = stosy_stos1_sum[i-1] + stosy_stos1[i];
    ind maxW=0;
    FOR(stos_idx,0,ind(stosy.size())-1){
        ind local_stos_sum=0;
        FOR(placek_idx,-1,ind(stosy[stos_idx].size())-1){
            if(placek_idx > M-1) continue;
            if(placek_idx != -1)
            local_stos_sum += stosy[stos_idx][placek_idx];
            ind min_stos_taken = -1;
            ind max_stos_taken = ind(stosy.size())-1;
            //todo: ogranicz przez K itd... nwm można potem w binsearchu chyba ale nwm
            while(min_stos_taken < max_stos_taken){
                if(max_stos_taken == stos_idx) {max_stos_taken--; continue;}
                if(min_stos_taken == stos_idx) {min_stos_taken++; continue;}
                ind center_stos_taken_l = (min_stos_taken+max_stos_taken-1)/2;
                ind center_stos_taken_r = (min_stos_taken+max_stos_taken+1)/2;
                if(center_stos_taken_l == stos_idx) center_stos_taken_l--;
                if(center_stos_taken_r == stos_idx) center_stos_taken_r++;

                ind w1 = 0;
                {
                w1 += local_stos_sum;
                if(center_stos_taken_l != -1) w1 += stosy_stos1_sum[center_stos_taken_l];
                ind usedk=(center_stos_taken_l+1)*M + (placek_idx+1);
                if(center_stos_taken_l >= stos_idx) {w1 -= stosy_stos1[stos_idx]; usedk -= M;}
                if(usedk > K) {max_stos_taken = center_stos_taken_l-1; continue;}
                
                if(K-usedk-1 != -1) w1 += stos_sum[K-usedk-1];
                }
                ind w2 = 0;
                {
                w2 += local_stos_sum;
                if(center_stos_taken_r != -1) w2 += stosy_stos1_sum[center_stos_taken_r];
                ind usedk=(center_stos_taken_r+1)*M + (placek_idx+1);
                if(center_stos_taken_r >= stos_idx) {w2 -= stosy_stos1[stos_idx]; usedk -= M;}
                if(usedk > K) {max_stos_taken = center_stos_taken_r-1; continue;}
                if(K-usedk-1 != -1) w2 += stos_sum[K-usedk-1];
                }
                maxW = max(maxW,w1);
                maxW = max(maxW,w2);


                if(w1 > w2) max_stos_taken = center_stos_taken_l;
                else min_stos_taken = center_stos_taken_r;
                //ind nalesniki_eaten
            }
            if(min_stos_taken<=-2) min_stos_taken=-1;//continue;
            //the code line below doesnt work
            if(min_stos_taken != -1) if(min_stos_taken>=stosy.size()) min_stos_taken = ind(stosy.size())-1;//continue;
                ind w1 = 0;
                {
                w1 += local_stos_sum;
                if(min_stos_taken != -1) w1 += stosy_stos1_sum[min_stos_taken];
                ind usedk=(min_stos_taken+1)*M + (placek_idx+1);
                if(min_stos_taken >= stos_idx) {w1 -= stosy_stos1[stos_idx]; usedk -= M;}
                if(usedk > K) {max_stos_taken = min_stos_taken-1; continue;}
                
                if(K-usedk-1 != -1) w1 += stos_sum[K-usedk-1];
                }
                maxW = max(maxW,w1);
        }
    }
    cout << maxW << endl;
    //if no partial stos...??
}