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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <climits>
#include <queue>
#include <numeric>
using namespace std;

int n, m, k;
vector<vector<long long>> V1, V2;
vector<long long> V3;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    V1.reserve(n);
    V2.reserve(n);
    V3.reserve(n);

    for (int i = 0; i < n; ++i){
        vector<long long> temp(m);
        for (int j = 0; j < m; ++j){
            cin >> temp[j];
        }
        if (temp.front() <= temp.back()){
            vector<long long> temp2(m + 1, 0);
            for (int j = 0; j < m; ++j){
                temp2[j + 1] = temp2[j] + temp[j];
            }
            V3.push_back(temp2[m]);
            V1.push_back(move(temp2));
        } else {
            V2.push_back(move(temp));
        }
    }

    vector<long long> inc(k + 1, LLONG_MIN), dec(k + 1, LLONG_MIN);
    inc[0] = 0;
    dec[0] = 0;

    int x = (int)V3.size();
    if (x > 0){
        vector<int> temp3(x);
        iota(temp3.begin(), temp3.end(), 0);

        sort(temp3.begin(), temp3.end(), [&](int a, int b){
            return V3[a] > V3[b];
        });

        vector<long long> pref(x + 1, 0);
        for (int i = 0; i < x; ++i){
            pref[i + 1] = pref[i] + V3[temp3[i]];
        }
        for (int i = 0; i <= x; ++i) {
            int y = i * m;
            if (y <= k){
                inc[y] = max(inc[y], pref[i]);
            }
        }

        vector<long long> suf2(x + 2, LLONG_MIN), pref2(x + 1, LLONG_MIN);

        for (int r = 1; r < m && r <= k; ++r) {
            suf2[x + 1] = LLONG_MIN;
            for (int i = x - 1; i >= 0; --i) {
                suf2[i + 1] = max(suf2[i + 2], V1[temp3[i]][r]);
            }

            pref2[0] = LLONG_MIN;
            long long act = LLONG_MIN;
            for (int i = 0; i < x; ++i) {
                act = max(act, V1[temp3[i]][r] - V3[temp3[i]]);
                pref2[i + 1] = act;
            }

            for (int i = 0; i < x; ++i) {
                int y = i * m + r;
                if (y > k){
                    break;
                }
                long long val = pref[i] + suf2[i + 1];
                if (i >= 1){
                    val = max(val, pref[i + 1] + pref2[i]);
                }
                inc[y] = max(inc[y], val);
            }
        }
    }

    if (!V2.empty()){
        priority_queue<pair<long long, int>> pq;
        vector<int> temp3(V2.size(), 0);

        for (int i = 0; i < (int)V2.size(); ++i){
            pq.push({V2[i][0], i});
        }

        long long act = 0;
        for (int t = 1; t <= k; ++t) {
            if (pq.empty()){
                break;
            }
            auto [v, id] = pq.top();
            pq.pop();
            act += v;
            dec[t] = act;
            ++temp3[id];
            if (temp3[id] < m){
                pq.push({V2[id][temp3[id]], id});
            }
        }
    }

    long long out = LLONG_MIN;
    for (int i = 0; i <= k; ++i){
        if (inc[i] == LLONG_MIN || dec[k - i] == LLONG_MIN){
            continue;
        }
        out = max(out, inc[i] + dec[k - i]);
    }

    cout << out << endl;
    return 0;
}