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

using namespace std;

typedef long long ll;

struct Stack {
    vector<ll> prefix_sums;
    ll total;
    int m;

    Stack(const vector<ll>& a) {
        m = a.size();
        prefix_sums.resize(m + 1, 0);
        for (int i = 0; i < m; ++i) {
            prefix_sums[i + 1] = prefix_sums[i] + a[i];
        }
        total = prefix_sums[m];
    }
};

bool compareStacks(const Stack& a, const Stack& b) {
    return a.total > b.total;
}

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

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

    vector<ll> pool_a;
    vector<Stack> stacks_b;

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

        if (current[0] >= current[m - 1]) {
            
            for (ll val : current) pool_a.push_back(val);
        } else {
            
            stacks_b.emplace_back(current);
        }
    }

    
    sort(pool_a.begin(), pool_a.end(), greater<ll>());
    vector<ll> pref_a(pool_a.size() + 1, 0);
    for (int i = 0; i < (int)pool_a.size(); ++i) {
        pref_a[i + 1] = pref_a[i] + pool_a[i];
    }

    // Przygotowanie Stosów B
    sort(stacks_b.begin(), stacks_b.end(), compareStacks);
    int nb = stacks_b.size();
    vector<ll> b_total_pref(nb + 1, 0);
    for (int i = 0; i < nb; ++i) {
        b_total_pref[i + 1] = b_total_pref[i] + stacks_b[i].total;
    }

    // BestB[y] - max suma biorąc dokładnie y naleśników ze stosów typu B
    vector<ll> best_b(min((ll)k, (ll)nb * m) + 1, 0);

    // Precomputacja maksimów dla częściowych stosów typu B
    // Dla każdego r (reszta z dzielenia y przez m) szukamy najlepszego stosu
    for (int r = 1; r < m; ++r) {
        vector<ll> max_prefix_suffix(nb + 1, -2e18); // max(P[j][r]) dla j >= i
        for (int i = nb - 1; i >= 0; --i) {
            max_prefix_suffix[i] = max(max_prefix_suffix[i + 1], stacks_b[i].prefix_sums[r]);
        }

        vector<ll> max_diff_prefix(nb + 1, -2e18); // max(P[j][r] - Total[j]) dla j < i
        for (int i = 0; i < nb; ++i) {
            max_diff_prefix[i + 1] = max(max_diff_prefix[i], stacks_b[i].prefix_sums[r] - stacks_b[i].total);
        }

        for (int p = 0; p <= nb; ++p) {
            ll y = (ll)p * m + r;
            if (y > k) break;

            ll option = -2e18;
            
            if (p < nb) {
                option = max(option, b_total_pref[p] + max_prefix_suffix[p]);
            }
            
            if (p > 0) {
                ll base = b_total_pref[p];
                if (p < nb) base += stacks_b[p].total;
                option = max(option, base + max_diff_prefix[p]);
            }
            
            if (y < best_b.size()) best_b[y] = option;
        }
    }

    
    for (int p = 0; p <= nb; ++p) {
        ll y = (ll)p * m;
        if (y <= k && y < (ll)best_b.size()) best_b[y] = b_total_pref[p];
    }

    ll ans = 0;
    for (int y = 0; y < (int)best_b.size(); ++y) {
        int rem_a = k - y;
        if (rem_a >= 0) {
            int take_a = min((int)pool_a.size(), rem_a);
            ans = max(ans, best_b[y] + pref_a[take_a]);
        }
    }

    cout << ans << endl;

    return 0;
}