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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>

const int maxn = 3e5+7;
const ll INF = 1e18;

bool czylatwe[maxn];
vector<ll> tab[maxn];
vector<ll> suma[maxn];
vector<ll> maxpref[maxn];
vector<ll> maxsuf[maxn];
ll sumpref[maxn];
ll numer[maxn];
ll wynlatwe[maxn];
ll wynreszta[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll n,m,k;
    cin>>n>>m>>k;

    ll a;
    for(int i=1;i<=n;i++){
        tab[i].pb(0);
        for(int j=1;j<=m;j++){
            cin>>a;
            tab[i].pb(a);
        }
        if(m == 1 || tab[i][1] >= tab[i][m])
            czylatwe[i] = 1;
    }

    priority_queue<pll> Q;
    for(int i=1;i<=n;i++){
        numer[i] = 1;
        if(czylatwe[i])
            Q.push({tab[i][1],i});
    }

    for(int i=1;i<=k;i++){
        wynlatwe[i] = wynlatwe[i-1];
        if(Q.size() == 0)
            continue;

        auto [x,ind] = Q.top();
        Q.pop();
        wynlatwe[i] += x;
        numer[ind]++;
        if(numer[ind] <= m)
            Q.push({tab[ind][numer[ind]],ind});
    }

    vector<pll> v;
    for(int i=1;i<=n;i++){
        if(czylatwe[i])
            continue;

        suma[i].pb(0);
        for(int j=1;j<=m;j++){
            suma[i].pb(suma[i][j-1]+tab[i][j]);            
        }
        v.pb({suma[i][m],i});
    }
    v.pb({INF,INF});
    sort(v.begin(),v.end(),greater<pll>());
    
    int ile = (int)v.size()-1;
    
    maxpref[0].resize(m+1,-INF);
    for(int i=1;i<=ile;i++){
        sumpref[i] = sumpref[i-1] + suma[v[i].nd][m];
        maxpref[i].resize(m+1,-INF);
        for(int j=1;j<=m;j++){
            maxpref[i][j] = max(maxpref[i-1][j],suma[v[i].nd][j]-suma[v[i].nd][m]);
        }
    }
    
    maxsuf[ile+1].resize(m+1,-INF);
    for(int i=ile;i>=1;i--){
        maxsuf[i].resize(m+1,-INF);
        for(int j=1;j<=m;j++){
            maxsuf[i][j] = max(maxsuf[i+1][j],suma[v[i].nd][j]);
        }
    }

    ll r;
    for(int i=1;i<=(ile*m);i++){
        a = i/m;
        r = i%m;
        wynreszta[i] = sumpref[a] + max((ll)0,maxsuf[a+1][r]);
        if(a < ile){
            wynreszta[i] = max(wynreszta[i],sumpref[a+1] + maxpref[a+1][r]);
        }
    }
    for(int i=ile*m+1;i<=k;i++){
        wynreszta[i] = wynreszta[i-1];
    }

    ll wyn = 0;
    for(int i=0;i<=k;i++){
        wyn = max(wyn,wynlatwe[i] + wynreszta[k-i]);
    }

    cout<<wyn<<"\n";

    return 0;
}