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
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
using namespace std;
const ll INF=1e18+7;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;ll k;
	cin>>n>>m>>k;
	vector<ll>wart;
	vector<vector<ll>>ros;
	for(int i=0;i<n;i++){
		vector<ll>s(m);bool maleje=1;
		for(int j=0;j<m;j++){
			cin>>s[j];if(j&&s[j-1]<s[j]) maleje=0;
		}
		if(maleje){
		for(ll e:s) wart.pb(e);}else{
			vector<ll>pr(m+1);
			for(int j=0;j<m;j++){
				pr[j+1]=pr[j]+s[j];
			}
			ros.pb(pr);
		}
	}
	sort(wart.begin(),wart.end(),greater<ll>());
	vector<ll>sumw(wart.size()+1);
	for(int i=0;i<wart.size();i++) sumw[i+1]=wart[i]+sumw[i];
	sort(ros.begin(),ros.end(),[m](const vector<ll>&a,const vector<ll>&b){
		return a[m]>b[m];
	});
	vector<ll>sums(ros.size()+1);
	for(int i=0;i<ros.size();i++) sums[i+1]=sums[i]+ros[i][m];
	vector<vector<ll>>sufm(ros.size()+1,vector<ll>(m+1,-INF));
	for(int i=ros.size()-1;i>-1;i--){
		for(int j=1;j<m;j++){
			sufm[i][j]=max(sufm[i+1][j],ros[i][j]);
		}
	}
	vector<vector<ll>>difm(ros.size()+1,vector<ll>(m+1,-INF));
	for(int i=0;i<ros.size();i++){
		for(int j=1;j<m;j++){
			ll dif=ros[i][j]-ros[i][m];
			difm[i][j]=(i==0)?dif:max(difm[i-1][j],dif);
		}
	}
	ll wyn=sumw[min(k,(ll)wart.size())];
	for(int i=0;i<=ros.size();i++){
		ll uz=(ll)m*i;
		if(uz<=k)
			wyn=max(wyn,sums[i]+sumw[min(k-uz,(ll)wart.size())]);
		for(int j=1;j<m;j++){
			ll cu=(ll)i*m+j;
			if(cu>k)break;
			ll zysk=sumw[min(k-cu,(ll)wart.size())];
			if(i<ros.size()&&sufm[i][j]!=-INF)
				wyn=max(wyn,sums[i]+sufm[i][j]+zysk);
			if(i<ros.size()&&difm[i][j]!=-INF)
				wyn=max(wyn,sums[i+1]+difm[i][j]+zysk);
		}
	}
	cout<<wyn<<'\n';
	return 0;
}