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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

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

    int n, m;
    ll k;
    if (!(cin >> n >> m >> k)) return 0;

    vector<ll> malejace_all;
    vector<pair<ll, vector<ll>>> rosnace_stosy;

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

        if (temp[0] >= temp[m - 1]) {
            for (ll val : temp) malejace_all.push_back(val);
        } else {
            ll suma = 0;
            for (ll val : temp) suma += val;
            rosnace_stosy.push_back({suma, temp});
        }
    }

    sort(malejace_all.rbegin(), malejace_all.rend());
    
    vector<ll> pref_malejace(malejace_all.size() + 1, 0);
    for (int i = 0; i < (int)malejace_all.size(); ++i) {
        pref_malejace[i + 1] = pref_malejace[i] + malejace_all[i];
    }

    sort(rosnace_stosy.rbegin(), rosnace_stosy.rend());

    int nr = rosnace_stosy.size();
    vector<ll> pref_rosnace(nr + 1, 0);
    for (int i = 0; i < nr; ++i) {
        pref_rosnace[i + 1] = pref_rosnace[i] + rosnace_stosy[i].first;
    }

    ll max_wynik = 0;

    for (int x = 0; x <= nr; ++x) {
        ll zuzyte_k = (ll)x * m;
        if (zuzyte_k > k) break;

        ll zostalo_k = k - zuzyte_k;
        ll l_malejace = min((ll)malejace_all.size(), zostalo_k);
        
        max_wynik = max(max_wynik, pref_rosnace[x] + pref_malejace[l_malejace]);
    }

    for (int i = 0; i < nr; ++i) {
        
        ll suma_czesciowa = 0;
        for (int p = 1; p < m; ++p) {
            suma_czesciowa += rosnace_stosy[i].second[p - 1];
            ll reszta_k = k - p;
            if (reszta_k < 0) break;

            ll x_pelnych = min((ll)nr - 1, reszta_k / m);
            
            ll suma_pelnych = 0;
            if (i < x_pelnych) {
                suma_pelnych = pref_rosnace[x_pelnych + 1] - rosnace_stosy[i].first;
            } else {
                suma_pelnych = pref_rosnace[x_pelnych];
            }

            ll zostalo_na_malejace = reszta_k - (x_pelnych * m);
            ll l_malejace = min((ll)malejace_all.size(), zostalo_na_malejace);

            max_wynik = max(max_wynik, suma_czesciowa + suma_pelnych + pref_malejace[l_malejace]);
        }
    }

    cout << max_wynik << "\n";

    return 0;
}