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 <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;

const ll NEG_INF = -4e18;

int main() {
    int n, m;
    ll k;
    scanf("%d %d %lld", &n, &m, &k);

    vector<vector<ll>> top(n, vector<ll>(m + 1, 0)); //prefix sum
    vector<ll> total(n);
    vector<ll> singles;
    int NI = 0;

    for (int i = 0; i < n; i++) {
        vector<ll> values;
        ll last = 0;
        bool decrease = false;

        for (int j = 0; j < m; j++) {
            ll x;
            scanf("%lld", &x);
            values.push_back(x);
            decrease = decrease | (x < last);
            last = x;
        }

        if (decrease) {
            for (ll v : values) {
                singles.push_back(v);
            }
        } else {
            for (int j = 0; j < m; j++) { 
                top[NI][j + 1] = top[NI][j] + values[j];
            }
            total[NI] = top[NI][m];
            NI++;
        }
    }

    // From bigger stack
    vector<int> ord(NI);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return total[a] > total[b];
    });
    
    vector<ll> prefix(NI + 1, 0); //top-q stacks
    for (int q = 0; q < NI; q++)
        prefix[q + 1] = prefix[q] + total[ord[q]];

    // smax[q*m + r] = max{ top[ord[t]][r] : t >= q }
    vector<ll> smax((NI + 1) * m, NEG_INF);
    for (int q = NI - 1; q >= 0; q--) {
        int t = ord[q];
        for (int r = 1; r < m; r++)
            smax[q * m + r] = max(smax[(q + 1) * m + r], top[t][r]);
    }

    // padj[q*m + r] = max{ top[ord[t]][r] - total[ord[t]] : t < q }
    vector<ll> padj((NI + 1) * m, NEG_INF);
    for (int q = 1; q <= NI; q++) {
        int t = ord[q - 1];
        for (int r = 1; r < m; r++)
            padj[q * m + r] = max(padj[(q - 1) * m + r], top[t][r] - total[t]);
    }

    //sort singles
    std::sort(singles.begin(), singles.end(), std::greater<ll>());

    ll result = 0;
    ll singles_sum = 0;
    for (int x = 0; x<=singles.size(); ++x) {
        if (x>0) {
            singles_sum += singles[x-1];
        }

        if (x + NI * m < k || x>k) {
            continue;
        }

        int q = (k-x) / m;
        int r = (k-x) % m;
        ll ans = 0;
        if (r == 0) {
            ans = prefix[q];
        } else {
            ll case1 = smax[q * m + r] + prefix[q];
            ll case2 = padj[q * m + r] + prefix[q + 1];
            ans = max(case1, case2);
        }

        result = std::max(result, singles_sum + ans);
    }

    printf("%lld\n", result);
    return 0;
}