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
136
137
138
139
140
141
142
143
144
145
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    long long n,m,k,ans = 0,a;
    cin>>n>>m>>k;
    vector< vector<long long> > V;
    vector<long long> v;
    for(int i=0; i<n; ++i) V.push_back(v);
    for(int i=0; i<n; ++i) {
        for(int j=0; j<m; ++j) {
            cin>>a;
            V[i].push_back(a);
        }
    }
    vector< pair<long long, vector<long long> > > W;
    vector<long long> S;
    for(int i=0; i<n; ++i) {
        if(V[i][0] < V[i][m-1]) {
            long long s = 0;
            for(int j=0; j<m; ++j) s += V[i][j];
            W.push_back(make_pair(s,V[i]));
        }
        else {
            for(int j=0; j<m; ++j) S.push_back(V[i][j]);
        }
    }
    sort(W.begin(),W.end());
    sort(S.begin(),S.end());
    int w = W.size() - 1,s1,s2;
    s1 = s2 = S.size() - 1;
    vector<long long> P,Suma;
    long long r = 0;
    for(int j=0; j<m; ++j) P.push_back(0);
    for(int i=0; i<S.size(); ++i) {
        r += S[i];
        Suma.push_back(r);
    }
    bool cz = true;
    while(k >= m) {
        if(w == -1) {
            ans += S[s1];
            s1--;
            k--;
            continue;
        }
        if(cz) {
            long long suma = 0;
            for(int j=0; j<m; ++j) {
                suma += W[w].second[j];
                P[j] = suma;
            }
            bool cz2 = true;
            for(int j=0; j<m; ++j) {
            //cout<<W[w].first<<" "<<P[m-1-j]<<" "<<Suma[s1]<<" "<<Suma[s1-j]<<endl;
                if(((s1-j >= 0) && (P[m-1-j] + Suma[s1] - Suma[s1-j] > W[w].first))
                || ((s1-j == -1) && (s1 >= 0) && (P[m-1-j] + Suma[s1] > W[w].first))
                || ((s1-m >= 0) && (j == m-1) && (Suma[s1] - Suma[s1-m] > W[w].first))
                || ((s1-m == -1) && (j == m-1) && (Suma[s1] > W[w].first))) {
                    s2 = s1 - j;
                    ans += S[s1]; //cout<<S[s1]<<endl;
                    s1--;
                    k--;
                    cz2 = false;
                    cz = false;
                    break;
                }
            }
            if(cz2) {
                ans += W[w].first; //cout<<W[w].first<<endl;
                w--;
                s2 = s1;
                k -= m;
            }
        }
        else {
            bool cz2 = true;
            for(int j=s1-s2; j<m; ++j) {
                if(((s1-j >= 0) && (P[m-1-j] + Suma[s1] - Suma[s1-j] > W[w].first))
                || ((s1-j == -1) && (s1 >= 0) && (P[m-1-j] + Suma[s1] > W[w].first))
                || ((s1-m >= 0) && (j == m-1) && (Suma[s1] - Suma[s1-m] > W[w].first))
                || ((s1-m == -1) && (j == m-1) && (Suma[s1] > W[w].first))) {
                    s2 = s1 - j;
                    ans += S[s1]; //cout<<S[s1]<<endl;
                    s1--;
                    k--;
                    cz2 = false;
                    break;
                }
            }
            if(cz2) {
                ans += W[w].first; //cout<<W[w].first<<endl;
                w--;
                s2 = s1;
                k -= m;
                cz = true;
            }
        }
        //cout<<ans<<endl;
    }
    long long MAx = 0;
    long long Max = 0;
    if((s1-k >= 0) && (s1 >= 0)) Max = max(Suma[s1] - Suma[s1-k],Max);
    if((s1-k == -1) && (s1 >= 0)) Max = max(Suma[s1],Max);
    MAx = max(Max,MAx);
    for(int i=w; i>=0; --i) {
        long long H = 0;
        for(int j=0; j<k; ++j) {
            H += W[i].second[j];
            if(s1-k+j+1 >= 0) Max = max(H + Suma[s1] - Suma[s1-k+j+1],Max);
            if((s1-k+j+1 == -1) && (s1 >= 0)) Max = max(H + Suma[s1],Max);
        }
        Max = max(H,Max);
        MAx = max(Max,MAx);
    }
    if(w >= 0) 
    for(int i=w+1; i<W.size(); ++i) {
        long long H = W[w].first - W[i].first;
        for(int j=0; j<k; ++j) {
            H += W[i].second[j];
            if(s1-k+j+1 >= 0) Max = max(H + Suma[s1] - Suma[s1-k+j+1],Max);
            if((s1-k+j+1 == -1) && (s1 >= 0)) Max = max(H + Suma[s1],Max);
        }
        Max = max(H,Max);
        MAx = max(Max,MAx);
    }
    ans += MAx;
    
    
    
    
    
    
    
    
    
    
    
    cout<<ans<<endl;
    
    return 0;
}