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
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 6e5 + 9, INF = 1e18;
ll n, m, K, f[N], g[N], c1, c2;
Ve<ll> a[N], pre[N];
bool ok[N];
Ve<ll> v1;
pii b[N];
ll len, pr[N], sf[N];
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), m = read(), K = read();
    rep(i, 1, n) a[i].resize(m + 2);
    rep(i, 1, n) {
        rep(j, 1, m) a[i][j] = read();
        ok[i] = 1;
        rep(j, 1, m - 1) ok[i] &= (a[i][j] >= a[i][j + 1]);
        if(ok[i]) {
            c1++;
            rep(j, 1, m) v1.pb(a[i][j]);
        }
        else {
            c2++;
            pre[i].resize(m + 2);
            rep(j, 1, m) pre[i][j] = pre[i][j - 1] + a[i][j];
        }
    }
    sort(ALL(v1), greater<ll>());
    rep(r, 0, m - 1) {
        len = 0;
        rep(i, 1, n) {
            if(!ok[i]) b[++len] = {pre[i][m], pre[i][r]};
        }
        sort(b + 1, b + len + 1, greater<pii>());
        pr[0] = -INF;
        rep(i, 1, len) pr[i] = max(pr[i - 1], b[i].second - b[i].first);
        sf[len + 1] = -INF;
        per(i, len, 1) sf[i] = max(sf[i + 1], b[i].second);
        ll sum = 0;
        rep(i, 0, len - 1) {
            ll cnt = i * m + r;
            f[cnt] = max(f[cnt], sum + sf[i + 1]);
            sum += b[i + 1].first;
        }
        sum = 0;
        rep(i, 1, len) {
            ll cnt = (i - 1) * m + r;
            sum += b[i].first;
            f[cnt] = max(f[cnt], sum + pr[i]);
            if(!r) f[len * m] = max(f[len * m], sum); 
        }
    }
    ll cnt = 0, sum = 0;
    for(ll x : v1) ++cnt, sum += x, g[cnt] = max(g[cnt], sum);
    ll ans = 0;
    rep(i, 0, min(K, cnt)) ans = max(ans, g[i] + f[min(c2 * m, K - i)]);
    write(ans), putchar('\n'); 
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}