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
#include <functional>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    vector<vector<int64_t>> incPref;
    vector<int64_t> bestDec;
    for (int i = 0; i < n; i++) {
        bool increasing = true;
        vector<int64_t> row(m + 1);
        for (int j = 1; j <= m; j++) {
            cin >> row[j];
            if (j > 1 && row[j - 1] > row[j]) increasing = false;
        }
        if (increasing) {
            vector<int64_t> pref(m + 1);
            for (int j = 1; j <= m; j++) {
                pref[j] = pref[j - 1] + row[j];
            }
            incPref.push_back(std::move(pref));
        } else {
            for (int j = 1; j <= m; j++) bestDec.emplace_back(row[j]);
        }
    }

    int cntInc = incPref.size();
    int szInc = cntInc * m;
    sort(bestDec.begin(), bestDec.end(), greater<int64_t>());
    for (int i = 1; i < (int)bestDec.size(); i++) bestDec[i] += bestDec[i - 1];

    vector<pair<int64_t,int>> ord;
    for (int i = 0; i < cntInc; i++) ord.emplace_back(incPref[i][m], i);
    sort(ord.begin(), ord.end(), greater<pair<int64_t,int>>());

    vector<int64_t> full(cntInc + 1);
    for (int i = 0; i < cntInc; i++) full[i + 1] = full[i] + ord[i].first;

    vector<int64_t> bestInc(szInc + 1);
    for (int q = 0; q <= cntInc; q++) bestInc[q * m] = full[q];

    for (int r = 1; r < m; r++) {
        vector<int64_t> prefBest(cntInc + 1), sufBest(cntInc + 1);
        for (int i = 0; i < cntInc; i++) {
            int id = ord[i].second;
            int64_t cur = incPref[id][r] - incPref[id][m];
            prefBest[i + 1] = (i == 0 ? cur : max(prefBest[i], cur));
        }
        for (int i = cntInc - 1; i >= 0; i--) {
            int id = ord[i].second;
            int64_t cur = incPref[id][r];
            sufBest[i] = (i == cntInc - 1 ? cur : max(sufBest[i + 1], cur));
        }
        for (int q = 0; q < cntInc; q++) {
            int64_t cur = full[q] + sufBest[q];
            if (q > 0) cur = max(cur, full[q + 1] + prefBest[q]);
            bestInc[q * m + r] = cur;
        }
    }

    int64_t res = 0;
    for (int i = 0; i <= k; i++) {
        if (i <= szInc && k - i <= (int)bestDec.size()) {
            int64_t cur = bestInc[i];
            if (k - i > 0) cur += bestDec[k - i - 1];
            res = max(res, cur);
        }
    }
    cout << res << '\n';
    return 0;
}
/*

2 2 4
1 2
1 3

3 3 5
1 2 3
1 2 3
3 2 1

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

*/