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
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; ++i)
#define RFOR(i, a, b) for(int i = (int)a; i >= (int)b; --i)
#define in insert
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;

ll gc() {
    char x; 
    while(true) {
        x = getchar_unlocked();
        if(x >= '0' && x <= '9') break;
    }
    ll num = x - '0';
    while(true) {
        x = getchar_unlocked();
        if(x >= '0' && x <= '9') {
            num *= 10;
            num += (x - '0');
        } else break;
    }
    return num;
}

bool cmp(const pair<ll, ll> &a, const pair<ll, ll> &b) {
    return a.fi > b.fi;
}

vector<vector<ll>> tab, mp, ms;

void solve() {
    ll n = gc(), m = gc(), k = gc();
    vector<ll> ws(1), sums(1);
    tab.assign(n + 5, vector<ll>(m + 5));
    mp.assign(n + 5, vector<ll>(m + 5));
    ms.assign(n + 5, vector<ll>(m + 5));
    ll idx = 0;
    FOR(i, 0, n + 4) FOR(j, 0, m + 4) ms[i][j] = 1e18;
    //wczytaj
    FOR(i, 1, n) {
        vector<ll> hlp(1);
        FOR(j, 1, m) {
            ll x = gc();
            hlp.pb(x);
        }
        if(hlp[1] < hlp[m]) {
            ++idx;
            FOR(j, 1, m) tab[idx][j] = hlp[j];
        } else {
            FOR(j, 1, m) ws.pb(hlp[j]);
        }
    }
    //przygotuj inne rzeczy
    vector<pair<ll, ll>> pr(1);
    FOR(i, 1, idx) {
        ll sum = 0;
        FOR(j, 1, m) sum += tab[i][j];
        pr.pb({sum, i});
    }
    sort(pr.begin() + 1, pr.end(), cmp);
    pr.pb({0, 0});
    //minima sufiksowe (liczone z gory na dol)
    FOR(i, 1, idx) {
        ll sum = 0, ind = pr[i].se;
        RFOR(j, m, 1) {
            sum += tab[ind][j];
            ms[i][j] = min(ms[i - 1][j], sum);
        }
    }
    //maxima prefiksowe (liczone z doly do gory)
    RFOR(i, idx, 1) {
        ll sum = 0, ind = pr[i].se;
        FOR(j, 1, m) {
            sum += tab[ind][j];
            mp[i][j] = max(mp[i + 1][j], sum);
        }
    }
    sort(ws.begin() + 1, ws.end(), greater<ll>());
    FOR(i, 1, ws.size() - 1) sums.pb(sums[i - 1] + ws[i]);
    //glowna czesc
    ll res = 0;
    FOR(i, 1, pr.size() - 2) pr[i].fi += pr[i - 1].fi;
    ll rozm = min(k, (ll)ws.size() - 1);
    FOR(i, 0, rozm) {
        ll sum1 = sums[i], z = min(idx * m, k - i);
        ll q = z / m, rst = z - (q * m);
        ll sum2 = pr[q].fi + mp[q + 1][rst];
        rst = ((q + 1) * m) - z;
        ll sum3 = pr[q + 1].fi - ms[q][m - rst + 1];
        res = max(res, sum1 + max(sum2, sum3));
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}