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
#include <bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define be(X) X.begin(), X.end()
#define pii pair<int,int>
#define V vector
#define f first
#define s second
#define ll long long
using namespace std;

V<V<ll>> pref;
V<V<ll>> suf;

V<pair<ll,V<ll>>> tab;
V<ll> war;
ll sumy[300009];

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

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

    F(i, 0, n-1){
        V<ll> wie;
        ll sum = 0;
        bool czy = 1;

        F(j, 1, m){
            ll x;
            cin >> x;
            sum+= x;
            if(wie.size() > 0 && x > wie.back()) czy = 0;
            wie.pb(x);
        }
        
        if(czy){
            for(auto x : wie){
                war.pb(x);
            }
        }
        else{
            tab.pb({sum, wie});
        }
    }

    sort(tab.begin(), tab.end(), [](auto &a, auto &b){
        return a.first > b.first;
    });

    sort(war.begin(), war.end());
    reverse(war.begin(), war.end());


    int it = 1;
    for(auto x : tab){
        sumy[it] = sumy[it-1] + x.first;
        it++; 
    }


    suf.resize(tab.size());

    F(i, 0, (int)tab.size()-1){
        suf[i].resize(m);
        ll sum = 0;

        R(j, m-1, 0){
            sum += tab[i].second[j];
            if(i == 0) suf[i][j] = sum;
            else suf[i][j] = min(suf[i-1][j], sum);
        }
    }

    pref.resize(tab.size());

    R(i, (int)tab.size()-1, 0){
        pref[i].resize(m);
        ll sum = 0;

        F(j, 0, m-1){
            sum += tab[i].second[j];
            if(i == (int)tab.size()-1) pref[i][j] = sum;
            else pref[i][j] = max(pref[i+1][j], sum);
        }
    }

    V<ll> prefw(war.size()+1, 0);
    F(i, 1, (int)war.size()){
        prefw[i] = prefw[i-1] + war[i-1];
    }

    ll ans = 0;

    F(x, max(0, k - (int)tab.size() * m), min((int)war.size(), k)){
        int y = (k - x) / m;
        int r = (k - x) % m;

        if(r == 0){
            if(y <= (int)tab.size()) ans = max(ans, prefw[x] + sumy[y]);
        }
        else{
            if(y < (int)tab.size()) ans = max(ans, prefw[x] + sumy[y] + pref[y][r-1]);
            if(y + 1 <= (int)tab.size()) ans = max(ans, prefw[x] + sumy[y+1] - suf[y][r]);
        }
    }

    cout << ans;
}