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
#include <bits/stdc++.h>
#define LL long long
int N,M,K,cq,p[300009];
LL a[300009],cc[300009],su[300009],s1[300009],ss[300009],as[300009];
bool cmp(int x,int y) {
	return su[x]>su[y];
}
inline int id(int x,int y) {
	x=x*M+y-M;
	return x;
}
signed main(void) {
	scanf("%d %d %d",&N,&M,&K);
	for(int i=1;i<=N;i++) {
		for(int j=1;j<=M;j++) {
			int x=id(i,j);
			scanf("%lld",&a[x]);
		}
		bool f1=0;
		for(int j=1;j<M;j++) {
			if(a[id(i,j)]>a[id(i,j+1)]) {
				f1=1;
				break;
			}
		}
		if(f1) {
			for(int j=1;j<=M;j++) {
				cc[++cq]=a[id(i,j)];
				a[id(i,j)]=0;
			}
			continue;
		}
		for(int j=1;j<=M;j++) {
			su[i]+=a[id(i,j)];
		}
	}
	for(int j=1;j<=N;j++) p[j]=j;
	std::sort(p+1,p+N+1,cmp);
	LL s2=0;
	for(int j=1;j<=N;j++) {
		s1[j]=s1[j-1]+su[p[j]];
	}
	for(int j=1;j<=M;j++) {
		for(int k=1;k<=N;k++) {
			ss[k]+=a[id(k,j)];
		}
		LL ma=0;
		for(int k=N;k>=1;k--) {
			ma=std::max(ma,ss[p[k]]);
			as[(k-1)*M+j]=std::max(as[(k-1)*M+j],ma+s1[k-1]);
		}
		ma=-0x3f3f3f3f3f3f3f3f;
		for(int k=1;k<=N;k++) {
			ma=std::max(ma,ss[p[k]]-su[p[k]]);
			as[(k-1)*M+j]=std::max(as[(k-1)*M+j],ma+s1[k]);
		}
	}
	std::sort(cc+1,cc+cq+1);
	std::reverse(cc+1,cc+cq+1);
	LL su=0,aa=0;
	for(int i=0;i<=cq;i++) {
		su+=cc[i];
		if(i<=K) aa=std::max(aa,su+as[K-i]);
	}
	printf("%lld",aa);
}