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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=3e5+5;

#define gc getchar_unlocked
#define pc putchar_unlocked
inline ll read(){
    ll x=0; char c=gc();
    while(!isdigit(c))c=gc();
    while(isdigit(c))x=x*10+c-'0',c=gc();
    return x;
}
void write(const ll x){
    if(x>9)write(x/10);
    pc(x%10+'0');
}

int n,m,k,cvf,cvg,p[N],cp;
ll _a[N],*a[N],s[N],s1[N],s2[N];
ll vf[N],f[N],g[N],ans;

int main(){
    n=read(),m=read(),k=read();
    for(int i=0;i<n;i++){
        a[i]=_a+i*m;
        for(int j=0;j<m;j++)a[i][j]=read();
        if(is_sorted(a[i],a[i]+m))p[cp++]=i,s[i]=accumulate(a[i],a[i]+m,0ll);
        else for(int j=0;j<m;j++)vf[cvf++]=a[i][j];
    }
    sort(p,p+cp,[&](int i,int j){return s[i]>s[j];});
    for(int i=0;i<cp;i++)s1[i+1]=s1[i]+s[p[i]];
    for(int i=cp-1,x;~i;i--){
        x=p[i],partial_sum(a[x],a[x]+m,a[x]);
        for(int j=0;j<m;j++)s2[j+1]=max(s2[j+1],a[x][j]);
        for(int j=0;j<m;j++)g[i*m+j]=s1[i]+s2[j];
    }
    fill_n(s2+1,m,1e18);
    for(int i=0,x;i<cp;i++){
        x=p[i];
        for(int j=0;j<m;j++)s2[j+1]=min(s2[j+1],a[x][m]-a[x][j]);
        for(int j=0;j<m;j++)g[i*m+j]=min(g[i*m+j],s1[i+1]-s2[j]);
    }
    sort(vf,vf+cvf,greater<ll>()),partial_sum(vf,vf+cvf,f+1),g[cvg=cp*m]=s1[cp];
    for(int i=0;i<=k;i++)ans=max(ans,f[min(i,cvf)]+g[min(k-i,cvg)]);
    write(ans),pc('\n');
    return 0;
}