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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
#define fi first
#define se second
#define each(a,x) for(auto &a:x)
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define nl '\n'
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi")
#pragma GCC target("bmi2")
#pragma GCC target("lzcnt")
#pragma GCC target("popcnt")
const int N = 5e5+1234,INF = 2e9+1234,mod = 1e9+7;
const ll INF_L = (ll)2e18+1234;
void solve()
{
    ll n,m,k;cin>>n>>m>>k;vector<vector<ll>> A,A2;A.assign(n,{});A2.assign(n,{});
    vector<ll> V;vector<pair<ll,ll>> V2;
    rep(i,n)
    {
        A[i].assign(m,-1);A2[i].assign(m,-1);rep(j,m) cin>>A[i][j],A2[i][j]=A[i][j];
        if(A[i][0]>=A[i][m-1]){rep(j,m) V.pb(A[i][j]);}
        else
        {
            reverse(all(A2[i]));
            for(int j=1;j<m;++j) A[i][j]+=A[i][j-1],A2[i][j]+=A2[i][j-1];
            V2.pb({A[i][m-1],i});
        }
    }
    sort(all(V));reverse(all(V));sort(all(V2));reverse(all(V2));ll ans=0;
    vector<vector<ll>> MX,MN; MN.assign(n,{});MX.assign(n,{});
    vector<ll> SU; SU.assign(n,0);
    rep(i,(int)V2.size())
    {
        SU[i]=V2[i].first;
        if(i>0) SU[i]+=SU[i-1];
        MN[i].assign(m,-1);
        rep(j,m)
        {
            MN[i][j]=A2[V2[i].second][j];
            if(i>0) MN[i][j]=min(MN[i][j],MN[i-1][j]);
        } 
    }
    for(int i=(int)V2.size()-1;i>=0;--i)
    {
        MX[i].assign(m,-1);
        rep(j,m)
        {
            MX[i][j]=A[V2[i].second][j];
            if(i+1<(int)V2.size()) MX[i][j]=max(MX[i][j],MX[i+1][j]);
        } 
    }
    /*cout << "SIZ: " << endl;
    for(auto x:V) cout << x << ' ';
    cout << endl;*/
    ll dod=0;
    for(ll x=0;x<=k;++x)
    {
        ll cost=0,zost=k-x;
        if(zost>0 and !V2.empty())
        {
            if(zost>=m*V2.size()) cost=SU[(int)V2.size()-1];
            else
            {
                ll il=zost/m,reszt=zost%m;
                if(reszt==0) cost=SU[il-1];
                else if(il==0) cost=MX[0][reszt-1];
                else cost=max(SU[il-1]+MX[il][reszt-1],SU[il-1]-MN[il-1][m-reszt-1]+MX[il][m-1]);
            }
        }
        //cout << "X: " << x << " ZOST: " << zost << " COST: " << cost << " DOD: " << dod << " VAL: " << dod+cost << endl;
        ans=max(ans,dod+cost);
        if(x>=k or x>=(int)V.size()) break;
        dod+=V[x];
    }
    cout << ans << nl;
}
int main()
{ 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //cin >> T;
    while(T--) solve();
    return 0;
}