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
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif
#define deb(...) 0

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int nInput, m, k; // stosy, nalesniki per stosy, do zjedzenia
    cin >> nInput >> m >> k;

    vector<ll> freeNalesnikiPref;
    vector<vector<ll>> stosyPref;

    rep(_, nInput) {
        vector<ll> stos(m);
        rep(i, m) cin >> stos[i];

        if (stos.front() < stos.back()) {
            fwd(i, 1, m) stos[i] += stos[i-1];
            stosyPref.pb(move(stos));
        }
        else
            freeNalesnikiPref.insert(freeNalesnikiPref.end(), all(stos));
    }
    sort(freeNalesnikiPref.rbegin(), freeNalesnikiPref.rend());
    fwd(i, 1, sz(freeNalesnikiPref)) freeNalesnikiPref[i] += freeNalesnikiPref[i-1];

    auto sumFree = [&](int l, int r) -> ll {
        // assert(0 <= l && l <= r && r < sz(freeNalesnikiPref));
        return freeNalesnikiPref[r] - (l ? freeNalesnikiPref[l-1] : 0);
    };
    auto sumFreePref = [&](int cnt) -> ll {
        // assert(cnt >= 0);
        cnt = min(cnt, sz(freeNalesnikiPref));
        if (cnt == 0) return 0;
        return freeNalesnikiPref[cnt-1];
    };
    auto sumStos = [&](int id, int l, int r) -> ll {
        // assert(0 <= l && l <= r && r < m);
        return stosyPref[id][r] - (l ? stosyPref[id][l-1] : 0);
    };

    ll ans = sumFreePref(k);
    deb(m, k);
    deb(freeNalesnikiPref);
    deb(stosyPref);
    deb("only free", ans);

    fwd(ile, 1, min(m, k)+1) { // ile nalesnikow ze specjalnego stosu
        int takeSurelyFree = (k-ile) % m;
        int takeBags = (k-ile) / m;

        deb(ile, takeSurelyFree, takeBags);

        vi stosPosition(sz(stosyPref));
        vector<pair<ll, ll>> bagsTagged;
        vector<ll> bagsPref;
        rep(id, sz(stosyPref))
            bagsTagged.eb(sumStos(id, 0, m-1), id);
        for (int i = takeSurelyFree; i < sz(freeNalesnikiPref); i += m)
            bagsTagged.eb(sumFree(i, min(i+m, sz(freeNalesnikiPref)) - 1), -1);
        sort(bagsTagged.rbegin(), bagsTagged.rend());

        bagsPref.resize(sz(bagsTagged));
        rep(i, sz(bagsTagged)) {
            auto [v, id] = bagsTagged[i];
            if (id != -1) stosPosition[id] = i;
            bagsPref[i] = v + (i ? bagsPref[i-1] : 0);
        }

        deb("");
        deb(ile, bagsPref, bagsTagged, takeBags, takeSurelyFree);

        rep(id, sz(stosyPref)) {
            ll here = sumStos(id, 0, ile - 1) + sumFreePref(takeSurelyFree);

            int iBagsPref = takeBags - 1;
            iBagsPref = min(iBagsPref, sz(bagsPref) - 1);

            if (iBagsPref < 0) {}
            else if (iBagsPref >= stosPosition[id]) {
                iBagsPref = min(iBagsPref + 1, sz(bagsPref) - 1);
                ll h = bagsPref[iBagsPref] - sumStos(id, 0, m-1);
                here += h;
            }
            else {
                here += bagsPref[iBagsPref];
            }

            if (here > ans) {
                ans = here;
                deb(id, here);
            }
        }
    }

    cout << ans << endl;
    _Exit(0);
}