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
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

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

    int n, m;
    ll k;
    cin >> n >> m >> k;

    vector<vector<ll>> conc, conv;

    for (int i = 0; i < n; i++) {
        vector<ll> a(m);
        for (int j = 0; j < m; j++) cin >> a[j];
        if (a[0] >= a[m - 1])
            conc.push_back(a);
        else
            conv.push_back(a);
    }

    vector<ll> cmarg;
    cmarg.reserve((ll)conc.size() * m);
    for (auto& s : conc)
        for (ll v : s) cmarg.push_back(v);
    sort(cmarg.rbegin(), cmarg.rend());

    ll nc = (ll)cmarg.size();
    vector<ll> fc(nc + 1, 0);
    for (ll i = 0; i < nc; i++) fc[i + 1] = fc[i] + cmarg[i];

    int nV = (int)conv.size();

    if (nV == 0) {
        cout << fc[k] << "\n";
        return 0;
    }

    sort(conv.begin(), conv.end(), [&](const vector<ll>& a, const vector<ll>& b) {
        ll sa = 0, sb = 0;
        for (ll v : a) sa += v;
        for (ll v : b) sb += v;
        return sa > sb;
    });

    vector<ll> fp((ll)nV * (m + 1), 0);
    for (int j = 0; j < nV; j++)
        for (int r = 0; r < m; r++)
            fp[(ll)j * (m + 1) + r + 1] = fp[(ll)j * (m + 1) + r] + conv[j][r];

    vector<ll> fcp(nV + 1, 0);
    for (int j = 0; j < nV; j++)
        fcp[j + 1] = fcp[j] + fp[(ll)j * (m + 1) + m];

    const ll NEG_INF = LLONG_MIN / 2;
    vector<ll> B((ll)(nV + 1) * m, NEG_INF);
    for (int r = 0; r < m; r++)
        for (int p = nV - 1; p >= 0; p--) {
            ll val = fp[(ll)p * (m + 1) + r];
            ll nxt = B[(ll)(p + 1) * m + r];
            B[(ll)p * m + r] = (nxt == NEG_INF) ? val : max(val, nxt);
        }

    vector<ll> PG((ll)(nV + 1) * m, NEG_INF);
    for (int p = 1; p <= nV; p++) {
        int j = p - 1;
        ll fpjm = fp[(ll)j * (m + 1) + m];
        for (int r = 0; r < m; r++) {
            ll gain = fp[(ll)j * (m + 1) + r] - fpjm;
            ll prev = PG[(ll)(p - 1) * m + r];
            PG[(ll)p * m + r] = (prev == NEG_INF) ? gain : max(prev, gain);
        }
    }

    ll ans = NEG_INF;

    for (int p = 0; p <= nV; p++) {
        ll s_base = (ll)p * m;
        if (s_base > k) break;

        ll c = k - s_base;
        if (c <= nc)
            ans = max(ans, fcp[p] + fc[c]);

        for (int r = 1; r < m; r++) {
            ll s = s_base + r;
            if (s > k) break;
            c = k - s;
            if (c > nc) continue;

            if (p < nV) {
                ll Bval = B[(ll)p * m + r];
                if (Bval != NEG_INF)
                    ans = max(ans, fcp[p] + Bval + fc[c]);
            }

            if (p > 0 && p < nV) {
                ll PGval = PG[(ll)p * m + r];
                if (PGval != NEG_INF)
                    ans = max(ans, fcp[p + 1] + PGval + fc[c]);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}