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
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using i128=__int128_t;
void die(string S){puts(S.c_str());exit(0);}
int n,m,k;
vector<vector<ll>> A;
vector<vector<ll>> sa;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	vector<ll> total;
	for(int i=0;i<n;i++)
	{
		vector<ll> vec(m);
		for(auto &x:vec) cin>>x;
		int ok=1;
		for(int j=1;j<m;j++)
			if(vec[j-1]<vec[j])
				ok=0;
		if(ok)
			for(auto x:vec)
				total.pb(x);
		else
			A.pb(vec);
	}
	rsrt(total);
	vector<ll> ps={0};
	for(auto x:total) ps.pb(ps.back()+x);
	sort(ALL(A),[&](const auto &X,const auto &Y){return accumulate(ALL(X),0ll)>accumulate(ALL(Y),0ll);});
	sa.resize(sz(A));
	for(int i=0;i<sz(A);i++)
	{
		sa[i]={0};
		for(auto x:A[i]) sa[i].pb(sa[i].back()+x);
	}
	ll ans=0;
	for(int i=0;i<=m;i++)
	{
		vector<ll> pa={-1ll*inf*inf},qa={-1ll*inf*inf};
		for(int j=0;j<sz(A);j++)
			pa.pb(max(pa.back(),sa[j][i]-sa[j][m]));
		for(int j=sz(A)-1;j>=0;j--)
			qa.pb(max(qa.back(),sa[j][i]));
		vector<ll> ss={0};
		for(int j=0;j<sz(A);j++)
			ss.pb(ss.back()+sa[j][m]);
		for(int j=0;j<sz(A);j++) if(j*m+i<=k&&k-j*m-i<=sz(total))
		{
			ll val=max(ss[j+1]+pa[j+1],ss[j]+qa[sz(A)-j]);
			ans=max(ans,val+ps[k-j*m-i]);
		}
	}
	if(k<=sz(total)) ans=max(ans,ps[k]);
	cout<<ans<<'\n';
	return 0;
}