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
#include <bits/stdc++.h>
using namespace std;

template <typename T> void set_min(T& a, const T& b){
	if(b < a) a = b;
}
template <typename T> void set_max(T& a, const T& b){
	if(b > a) a = b;
}

using ll = int64_t;

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, M, K;
	cin >> N >> M >> K;
	vector<vector<ll> > inc, dec;
	for(int i = 0; i < N; i++){
		vector<ll> A(M);
		for(ll& x : A) cin >> x;
		if(A.front() <= A.back()){
			inc.push_back(A);
		} else {
			dec.push_back(A);
		}
	}
	vector<ll> all_dec;
	for(auto v : dec) all_dec.insert(all_dec.end(), v.begin(), v.end());
	sort(all_dec.rbegin(), all_dec.rend());

	vector<ll> score_dec = {0};
	for(ll x : all_dec){
		x += score_dec.back();
		score_dec.push_back(x);
	}

	int Z = (int)inc.size();
	vector<vector<ll>> all_psums(Z, vector<ll>(M+1, 0));
	for(int l = 0; l < M; l++){
		for(int i = 0; i < Z; i++){
			all_psums[i][l+1] = all_psums[i][l] + inc[i][l];
		}
	}
	vector<ll> score_inc(Z * M + 1, 0);
	for(int l = 0; l <= M; l++){
		vector<pair<ll,ll>> scores;
		for(int i = 0; i < Z; i++){
			scores.push_back({all_psums[i][M], all_psums[i][l]});
		}
		sort(scores.rbegin(), scores.rend());
		multiset<ll> full_to_extra;
		multiset<ll> extra;
		for(auto [take_all, take_l] : scores) extra.insert(take_l);
		ll full_sum = 0;
		for(int full_cnt = 0; full_cnt < Z; full_cnt++){
			set_max(score_inc[full_cnt * M + l], full_sum + *extra.rbegin());
			extra.erase(extra.find(scores[full_cnt].second));
			full_to_extra.insert(scores[full_cnt].second - scores[full_cnt].first);
			full_sum += scores[full_cnt].first;
			set_max(score_inc[full_cnt * M + l], full_sum + *full_to_extra.rbegin());
		}
	}
	ll ans = 0;
	for(int a = 0; a <= K; a++){
		int b = K-a;
		if(a < (int)score_dec.size() && b < (int)score_inc.size()){
			set_max(ans, score_dec[a] + score_inc[b]);
		}
	}
	cout << ans << '\n';
}