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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ssize(x) int((x).size())
ll inf = 1000000000000000000ll;

struct s_info {
    int i;
    ll s;

    bool operator<(const s_info st) const {
        return s > st.s;
    }
};

struct pq_info {
    ll v;
    int i, j;

    bool operator<(const pq_info p) const {
        return v < p.v;
    }
};

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

    vector <s_info> st0;
    priority_queue <pq_info> pq;

    vector <vector <ll> > a(n, vector <ll>(m));
    for(int i = 0; i < n; ++i) {
        int type = 1;
        ll sum = 0ll;

        for(int j = 0; j < m; ++j) {
            scanf("%lld", &a[i][j]);
            sum += a[i][j];
            if(j && a[i][j - 1] < a[i][j])
                type = 0;
        }

        if(type == 0)
            st0.pb({i, sum});
        else
            pq.push({a[i][0], i, 0});
    }

    // typ 1
    vector <ll> ans1(k + 1, 0ll);
    for(int k1 = 1; k1 <= k; ++k1) {
        ans1[k1] = ans1[k1 - 1];
        if(!pq.empty()) {
            pq_info p = pq.top();
            pq.pop();

            ans1[k1] += p.v;
            if(p.j + 1 < m)
                pq.push({a[p.i][p.j + 1], p.i, p.j + 1});
        }
    }

    // typ 0
    int n0 = ssize(st0);
    sort(st0.begin(), st0.end());

    vector <ll> sum(n0, 0ll);
    vector <vector <ll> > min_pref(n0, vector <ll>(m, inf)), max_suf(n0, vector <ll>(m, 0ll));
    for(int p = 0; p < n0; ++p) {
        s_info st = st0[p];
        sum[p] = st.s + (p ? sum[p - 1] : 0ll);
        ll s = 0ll;
        for(int j = m - 1; j >= 0; --j) {
            s += a[st.i][j];
            if(!p) min_pref[p][j] = s;
            else min_pref[p][j] = min(min_pref[p - 1][j], s);
        }
    }

    for(int p = n0 - 1; p >= 0; --p) {
        int i = st0[p].i;
        ll s = 0ll;
        for(int j = 0; j < m; ++j) {
            s += a[i][j];
            if(p + 1 == n0) max_suf[p][j] = s;
            else max_suf[p][j] = max(max_suf[p + 1][j], s);
        }
    }

    ll ans = ans1[k];
    for(int k0 = 1; k0 <= min(k, n0 * m); ++k0) {
        int w = k0 / m; // ile calych stosow

        if(!(k0 % m)) ans = max(ans, sum[w - 1] + ans1[k - k0]);
        else {
            ll ans0 = max_suf[w][(k0 % m) - 1];
            if(w) ans0 += sum[w - 1];

            ans0 = max(ans0, sum[w] - min_pref[w][m - ((w + 1) * m - k0)]);

            ans = max(ans, ans0 + ans1[k - k0]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}