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
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif


typedef long long ll;
typedef long double ld;

#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)

vector<int> read_vec(int n) {
    vector<int> v(n);
    for (int& t : v) cin >> t;
    return v;
}

template<typename T>
inline void upd_max(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

template<typename T>
inline void upd_min(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> inc;
    vector<ll> dec;
    FOR(i, 0, n) {
        vector<ll> b(m);
        FOR(z, 0, m) cin >> b[z];
        if (is_sorted(b.begin(), b.end())) inc.emplace_back(b);
        else {
            for (auto& it : b) dec.emplace_back(it);
        }
    }
    vector<ll> A(dec.size() + 1);
    sort(dec.rbegin(), dec.rend());
    FOR(i, 0, dec.size()) A[i + 1] = A[i] + dec[i];
    vector<ll> B(inc.size() * m + 1);
    vector<ll> tot(inc.size());
    vector<ll> cur(inc.size());
    FOR(z, 0, inc.size()) tot[z] = accumulate(inc[z].begin(), inc[z].end(), 0LL);
    FOR(res, 0, m) {
        vector<pair<ll,ll>> T;
        FOR(x, 0, inc.size()) T.emplace_back(tot[x], cur[x]);
        sort(T.rbegin(), T.rend());
        vector<ll> suf_max(T.size());
        for (int i = T.size() - 1; i >= 0; i--) {
            suf_max[i] = T[i].second;
            if (i + 1 < T.size()) upd_max(suf_max[i], suf_max[i + 1]);
        }
        ll cur_s = 0;
        ll max_b = -1e18;
        FOR(cnt_full, 0, inc.size()) {
            upd_max(B[cnt_full * m + res], suf_max[cnt_full] + cur_s);
            cur_s += T[cnt_full].first;
            upd_max(max_b, T[cnt_full].second - T[cnt_full].first);
            upd_max(B[cnt_full * m + res], cur_s + max_b);
        }
        FOR(x, 0, inc.size()) cur[x] += inc[x][res];
    }
    B[inc.size() * m] = accumulate(tot.begin(), tot.end(), 0LL);
    ll f = 0;
    FOR(d, 0, k + 1) {
        if (d < A.size() && k - d < B.size()) upd_max(f, A[d] + B[k - d]);
    }
    cout << f << '\n';
    return 0;
}