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
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
vector<ll> a[300005],b[300005];
vector<ll> pf[300005],sf[300005];
pll p[300005];
ll fa[300005],fb[300005];
ll al[300005];
ll ts[300005];
int main()
{
	ios_base::sync_with_stdio(0);
	int n,m,k=0,l;
	cin>>m>>n>>l;
	vector<ll> x(n);
	int t=0;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++) cin>>x[j];
		bool ge=1;
		for(int j=1;j<n;j++) ge&=x[j]<=x[j-1];
		if(ge) a[k++]=x;
		else b[t++]=x;
	}
	m=t;
	for(int i=0;i<m;i++)
	{
		for(ll j:b[i]) ts[i]+=j;
		p[i]=mp(ts[i],i);
	}
	sort(p,p+m);
	reverse(p,p+m);
	for(int i=0;i<=m;i++)
	{
		pf[i].resize(n+1);
		sf[i].resize(n+1,1e18);
	}
	for(int i=m-1;i>=0;i--)
	{
		for(int j=0;j<n;j++) pf[i][j+1]=pf[i][j]+b[p[i].s][j];
		for(int j=0;j<=n;j++) pf[i][j]=max(pf[i][j],pf[i+1][j]);
	}
//	for(int i=0;i<=m;i++)
//	{
//		for(int j=0;j<=n;j++) cout<<pf[i][j]<<' ';
//		cout<<endl;
//	}
	for(int i=0;i<m;i++)
	{
		sf[i+1][n]=0;
		for(int j=n-1;j>=0;j--) sf[i+1][j]=sf[i+1][j+1]+b[p[i].s][j];
		for(int j=0;j<=n;j++) sf[i+1][j]=min(sf[i+1][j],sf[i][j]);
	}
//	for(int i=0;i<=m;i++)
//	{
//		for(int j=0;j<=n;j++) cout<<sf[i][j]<<' ';
//		cout<<endl;
//	}
	ll cs=0;
	for(int i=0;i<m*n;i++)
	{
		fb[i]=cs+pf[i/n+1][i%n];
		if((i+1)%n==0) cs+=p[i/n].f;
	}
	for(int i=0;i<m*n;i++)
	{
		fb[m*n-i]=max(fb[m*n-i],cs-sf[m-i/n][n-i%n]);
		if((i+1)%n==0) cs-=p[m-i/n-1].f;
	}
	for(int i=0;i<k*n;i++) al[i]=a[i/n][i%n];
	sort(al,al+k*n);
	reverse(al,al+k*n);
	for(int i=0;i<k*n;i++) fa[i+1]=fa[i]+al[i];
	ll ans=0;
//	for(int i=0;i<=k*n;i++) cout<<fa[i]<<' ';
//	cout<<endl;
//	for(int i=0;i<=m*n;i++) cout<<fb[i]<<' ';
//	cout<<endl;
	for(int i=0;i<=k*n;i++) if(l-i>=0&&l-i<=m*n) ans=max(ans,fa[i]+fb[l-i]);
	cout<<ans<<endl;
	return 0;
}/*3 3 5
1 2 5
1 2 5
1 3 3
*/