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
#include<iostream>
#include<vector>
int n,m,k;
long long a;
std::vector<std::vector<long long> >ros;
std::vector<long long> poj;
std::vector<std::pair<long long,int> >sum_poz;
int main(){
	std::cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		std::vector<long long> st;
		long long sum=0;
		for(int j=0;j<m;j++){
			std::cin>>a;
			st.emplace_back(a);
			sum+=a;
		}
		if(st[0]<st[m-1]){
			ros.emplace_back(st);
			sum_poz.emplace_back(sum,ros.size()-1);
			}
		else
			for(int j=0;j<m;j++)
				poj.emplace_back(st[j]);
	}
	for(int i=0;i<m;i++)
		poj.emplace_back(0);
	sum_poz.emplace_back(0,-1);
	std::sort(poj.begin(),poj.end());
	std::sort(sum_poz.begin(),sum_poz.end());
	long long res=0;
	int i=poj.size()-1;
	int j=sum_poz.size()-1;
	while(true){
		if(poj[i]*m>sum_poz[j].first){
			res+=poj[i];
			i--;
			k--;
		}else{
			res+=sum_poz[j].first;
			j--;
			k-=m;
		}
		if(k<=0)
			break;
	}
	if(k==0){
		std::cout<<res<<std::endl;
		return 0;
	}
	j++;
	k+=m;
	//std::cout<<res<<std::endl;
	while(k>0){
		res+=poj[i];
		i--;
		k--;
	}
	i++;
	//std::cout<<res<<std::endl;
	long long best_res=0;
	for(int z=1;z<sum_poz.size();z++){
		int poz=sum_poz[z].second;
		long long best=0;
		long long sum=0;
		for(int r=0;r<m;r++){
			if(i+r<poj.size()){
				sum=sum+ros[poz][r]-poj[i+r];
				//std::cout<<"r ros poj "<<r<<" "<<ros[poz][r]<<" "<<poj[i+r]<<std::endl;
				if(sum>best)
					best=sum;
			}
		
		}
		//std::cout<<"best "<<best<<std::endl;
		long long pom=0;
		if(z<=j)
			pom=res+best-sum_poz[j].first;
		else
			pom=res+best-sum_poz[z].first;
		//std::cout<<"pom "<<pom<<std::endl;
		if(pom>best_res)
			best_res=pom;
	}
	std::cout<<best_res<<std::endl;
	return 0;
}