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
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

vector<ll> S1[300003];
ll T[300003];
vector<ll> K2;
vector<pair<ll, int> > SBS;
priority_queue<pair<ll, int> > pq1;
ll MX[300003];
int wpq[300003];

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

    int n, m, k;
    cin >> n >> m >> k;
    int k1s = 0;
    for (int i = 0; i < n; i++) {
        int kn = 0;
        for (int j = 0; j < m; j++) {
            cin >> T[j];
            if (j > 0 && T[j] < T[j - 1]) {
                kn = 1;
            }
        }
        if (kn == 0) {
            ll ss = 0;
            for (int j = 0; j < m; j++) {
                ss += T[j];
                S1[k1s].push_back(ss);
            }
            SBS.emplace_back(ss, k1s);
            k1s++;
        } else {
            for (int j = 0; j < m; j++) {
                K2.push_back(T[j]);
            }
        }
    }
    sort(SBS.begin(), SBS.end(), greater<>());
    sort(K2.begin(), K2.end(), greater<>());

    for (int i = 0; i < k1s; i++) {
        MX[(i + 1) * m] = MX[(i) * m] + SBS[i].first;
    }

    if (k1s > 0) {
        for (int i = 0; i < m - 1; i++) {
            while (!pq1.empty()) pq1.pop();
            for (int j = 0; j < k1s; j++) {
                pq1.emplace(S1[j][i], j);
                wpq[j] = 1;
            }
            MX[i + 1] = pq1.top().first;
            ll inc1 = 0;
            ll mx2 = -1000000000000000000L;
            for (int j = 0; j < k1s - 1; j++) {
                inc1 += SBS[j].first;
                ll inc2 = inc1 + SBS[j + 1].first;
                mx2 = max(mx2, S1[SBS[j].second][i] - SBS[j].first);
                wpq[SBS[j].second] = 2;
                while (wpq[pq1.top().second] == 2) pq1.pop();
                ll v1 = pq1.top().first + inc1;
                ll tm = max(v1, inc2 + mx2);
                MX[i + 1 + (j + 1) * m] = max(v1, tm);
            }
        }
    }

    int k2s = K2.size();
    int sw2 = min(k, k2s);
    ll mc = 0;
    for (int i = 0; i < sw2; i++) {
        mc += K2[i];
    }
    int sw1 = k - sw2;
    mc += MX[sw1];
    ll res = mc;
    for (int i = sw2 - 1; i >= 0; i--) {
        if (sw1 > k1s * m) break;
        mc -= K2[i];
        mc += MX[sw1 + 1] - MX[sw1];
        res = max(mc, res);
        sw1++;
    }
    cout << res << "\n";
    cout.flush();

    return 0;
}