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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<int>> ups;
vector<vector<int>> nups;
vector<vector<int>> downs;
vector<int> sups;
vector<pair<int,int>> zups;
int n,m;
int solvedown[300009];
vector<vector<int>> prefsum;
vector<vector<int>> suffsum;
vector<int> prefups;
vector<vector<int>> bestxonsuff;
vector<vector<int>> worstxonpref;

int solve_on_ups(int k) {
    int infull = k/m;
    int s = ups.size();
    infull = min(infull,s);
    if (infull == s) {
        return prefups[infull];
    }
    int ans = prefups[infull];
    if (k%m -1 >= 0) {
        ans += bestxonsuff[infull][k%m-1];
    }
    int ans2= 0;
    if (k%m > 0) {
        ans2 = prefups[infull+1];
        ans2 -= worstxonpref[infull+1][(k%m)];
    }
    return max(ans,ans2);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int k;
    cin>>n>>m>>k;
    vector<vector<int>> v;

    vector<bool> up;
    if (m == 1) {
        vector<int> q;
        for (int i = 0; i<n*m; i++) {
            int x;
            cin>>x;
            q.push_back(x);
        }
        sort(q.begin(), q.end(),greater<int>());
        int s = 0;
        for (int i = 0; i<k; i++) {
            s += q[i];
        }
        cout<<s<<"\n";
        return 0;
    }
    for(int i=0;i<n;i++) {
        v.emplace_back();
        int where = 0;
        for (int j = 0; j < m; j++) {
            int x;
            cin>>x;
            v[i].push_back(x);
            if (j != 0) {
                if (v[i][j] > v[i][j-1]) {
                    where = 1;
                }
            }
        }
        if (where == 1) {
            up.push_back(true);
            ups.push_back(v[i]);
            nups.emplace_back();
        }else {
            up.push_back(false);
            downs.push_back(v[i]);
        }
    }
    int i = 0;
    for (auto x: ups) {
        int h = 0;
        for (auto q : x) {
            h+=q;
        }
        sups.push_back(h);
        zups.push_back({h,i});
        i++;
    }
    sort(zups.begin(),zups.end(),greater<pair<int,int>>());
    for (int i = 0; i<zups.size(); i++) {
        nups[i] = ups[zups[i].second];
    }
    sort(sups.begin(), sups.end(),greater<int>());
    vector<int> d;
    for (auto x: downs) {
        for (auto y: x) {
            d.push_back(y);
        }
    }
    sort(d.begin(), d.end(),greater<int>());
    for (int i = 1; i<=k; i++) {
        if (i-1 < d.size()) {
            solvedown[i] = solvedown[i-1] + d[i-1];
        }else {
            solvedown[i] = solvedown[i-1];
        }
    }
    int best = 0;
    for (int i = 0; i<n; i++) {
        prefsum.emplace_back();
        suffsum.emplace_back();
        for (int j = 0; j<=m+1; j++) {
            prefsum[i].push_back(0);
            suffsum[i].push_back(0);
        }
    }
    int h = nups.size();
    for (int i = 1; i<=m; i++) {
        for (int j = 0; j<h; j++) {
            prefsum[j][i] = prefsum[j][i-1] + nups[j][i-1];
        }
    }
    for (int i = m; i>=1; i--) {
        for (int j = 0; j<h; j++) {
            suffsum[j][i] = suffsum[j][i+1] + nups[j][i-1];
        }
    }
    prefups.push_back(0);
    for (int i= 1; i<=h; i++) {
        prefups.push_back(prefups[i-1] + sups[i-1]);
    }
    for (int i = 0; i<=h; i++) {
        bestxonsuff.emplace_back();
        for (int j = 0; j<m; j++) {
            bestxonsuff[i].push_back(0);
        }
    }
    for (int i = h-1; i>=0; i--) {
        int s = 0;
        for (int j = 0; j<m; j++) {
            s += nups[i][j];
            bestxonsuff[i][j] = max(bestxonsuff[i][j], s);
            bestxonsuff[i][j] = max(bestxonsuff[i+1][j], bestxonsuff[i][j]);
        }
    }
    for (int i = 0; i<=h+1; i++) {
        worstxonpref.emplace_back();
        for (int j = 0; j<m; j++) {
            worstxonpref[i].push_back(LONG_LONG_MAX);
        }
    }
    for (int i = 1; i<=h; i++) {
        int s = 0;
        for (int j = m-1; j>=0; j--) {
            s += nups[i-1][j];
            worstxonpref[i][j] = min(worstxonpref[i][j], s);
            worstxonpref[i][j] = min(worstxonpref[i-1][j], worstxonpref[i][j]);
        }
    }
    for (int i = 0; i<=k; i++) {
        int a = solve_on_ups(i);
        int b = solvedown[k-i];
        best = max(best,a+b);
    }
    cout<<best<<"\n";
}