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
#include <bits/stdc++.h>

using namespace std;

int n, m;
long long k;

vector<long long> desc_pancakes, pref_desc, pref_asc;
vector<long long> val1, val2, pref_max, suff_max;
vector<vector<long long>> asc_stacks, pref_asc_stacks;
vector<pair<long long, int>> asc_order;

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

    cin >> n >> m >> k;

    for (int i = 0; i < n; ++i) {
        vector<long long> row(m);
        for (int j = 0; j < m; ++j) cin >> row[j];

        if (m == 1 || row[0] >= row[m - 1]) {
            for (auto x : row) desc_pancakes.push_back(x);
        } 
        else {
            asc_stacks.push_back(row);
        }
    }

    sort(desc_pancakes.rbegin(), desc_pancakes.rend());
    pref_desc.push_back(0);
    for (auto x : desc_pancakes) pref_desc.push_back(pref_desc.back() + x);

    for (int i = 0; i < (int)asc_stacks.size(); ++i) {
        long long s = 0;
        for (auto x : asc_stacks[i]) s += x;
        asc_order.push_back({s, i});
    }
    sort(asc_order.rbegin(), asc_order.rend());

    pref_asc.push_back(0);
    for (int i = 0; i < (int)asc_order.size(); ++i) {
        pref_asc.push_back(pref_asc.back() + asc_order[i].first);
        
        int idx = asc_order[i].second;
        vector<long long> cum_p; 
        cum_p.push_back(0);
        for (int j = 0; j < m; ++j) cum_p.push_back(cum_p.back() + asc_stacks[idx][j]);
        pref_asc_stacks.push_back(cum_p);
    }

    long long output = 0;
    int num_asc = asc_order.size();

    for (int p = 0; p < m; ++p) {
        if (p > 0 && num_asc > 0) {
            val1.assign(num_asc, 0); val2.assign(num_asc, 0);
            for (int i = 0; i < num_asc; ++i) {
                val1[i] = pref_asc_stacks[i][p] - asc_order[i].first;
                val2[i] = pref_asc_stacks[i][p];
            }

            pref_max.assign(num_asc, 0);
            pref_max[0] = val1[0];
            for (int i = 1; i < num_asc; ++i) pref_max[i] = max(pref_max[i - 1], val1[i]);

            suff_max.assign(num_asc, 0);
            suff_max[num_asc - 1] = val2[num_asc - 1];
            for (int i = num_asc - 2; i >= 0; --i) suff_max[i] = max(suff_max[i + 1], val2[i]);
        }

        for (long long C = 0; C <= num_asc; ++C) {
            long long rem = k - (C * m + p);
            if (rem < 0 || rem >= (long long)pref_desc.size()) continue;

            if (p == 0) {
                output = max(output, pref_asc[C] + pref_desc[rem]);
            } 
            else if (num_asc > 0 && C < num_asc) {
                long long best_asc = LLONG_MIN;
                best_asc = max(best_asc, pref_asc[C + 1] + pref_max[C]);
                best_asc = max(best_asc, pref_asc[C] + suff_max[C]);

                if (best_asc != LLONG_MIN) {
                    output = max(output, best_asc + pref_desc[rem]);
                }
            }
        }
    }

    // PLEASE WORK ;-;
    cout << output << endl;

    return 0;
}