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
// Zadanie: sto (Stosy naleśników)
// runda 2
// Marcin Machura <marcin.machura@hotmail.com>
//
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

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

    vector<ll> concave_vals; // story odwrócone: tam optymalne rozwiazanie jest zachalnne
    vector<vector<ll>> convex_prefs; // stosy zwykle, tu trzeba kombiniowac

    for (int i = 0; i < n; ++i) {
        vector<ll> a(m + 1);
        a[0] = 0;
        for (int j = 1; j <= m; ++j)
            scanf("%lld", &a[j]);

        vector<ll> pref(m + 1);
        pref[0] = 0;
        for (int j = 1; j <= m; ++j)
            pref[j] = pref[j - 1] + a[j];

        if (m <= 1 || a[1] >= a[m]) {
            for (int j = 1; j <= m; ++j)
                concave_vals.push_back(a[j]);
        } else {
            convex_prefs.push_back(pref);
        }
    }

    // g[b] = max wartość z wklęsłych stosów biorąc b
    sort(concave_vals.begin(), concave_vals.end(), greater<ll>());
    vector<ll> g(k + 1, 0);
    for (int b = 1; b <= k; ++b)
        g[b] = g[b - 1] + (b <= (int)concave_vals.size() ? concave_vals[b - 1] : 0);

    // Stosy wypukłe: posortowane po pref[m] malejąco, prefix sumy wartości
    int nc = (int)convex_prefs.size();
    vector<int> order(nc);
    for (int i = 0; i < nc; ++i) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) {
        return convex_prefs[a][m] > convex_prefs[b][m];
    });

    vector<ll> cv(nc + 1, 0);
    for (int t = 1; t <= nc; ++t)
        cv[t] = cv[t - 1] + convex_prefs[order[t - 1]][m];

    vector<int> rnk(nc);
    for (int r = 0; r < nc; ++r)
        rnk[order[r]] = r;

    ll ans = 0;

    
    int max_full = m > 0 ? min(nc, k / m) : 0;
    for (int t = 0; t <= max_full; ++t)
        ans = max(ans, cv[t] + g[k - t * m]);

    // zjedzony częściowo 
    if (m >= 2) {
        for (int i = 0; i < nc; ++i) {
            int r = rnk[i];
            ll full_val = convex_prefs[i][m];

            for (int x = 1; x < m && x <= k; ++x) {
                int rem = k - x;
                int max_t = min(nc - 1, rem / m);
                ll pref_x = convex_prefs[i][x];

                auto cv_excl = [&](int t) -> ll {
                    return t <= r ? cv[t] : cv[t + 1] - full_val;
                };
                auto h = [&](int t) -> ll {
                    return cv_excl(t) + pref_x + g[rem - t * m];
                };

                // Binsearch 
                int lo = 0, hi = max_t;
                while (lo < hi) {
                    int mid = lo + (hi - lo) / 2;
                    if (h(mid) < h(mid + 1))
                        lo = mid + 1;
                    else
                        hi = mid;
                }
                ans = max(ans, h(lo));
            }
        }
    }

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