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

using LL = long long;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> m >> k;
	vector<LL> easy;
	vector<vector<LL>> pref;
	for (int i = 0; i < n; i++) {
		vector<LL> row(m);
		for (LL& x : row) {
			cin >> x;
		}
		if (row[0] >= row.back()) {
			easy.insert(easy.end(), row.begin(), row.end());
		}
		else {
			vector<long long> p(m + 1);
			for (int j = 0; j < m; j++) {
				p[j+1] = p[j] + row[j];
			}
			pref.push_back(p);
		}
	}
	sort(pref.begin(), pref.end(), [&](const vector<LL>& a, const vector<LL>& b) { return a.back() > b.back(); });
	sort(easy.rbegin(), easy.rend());
	easy.insert(easy.begin(), 0LL);
	for (int i = 1; i < (int) easy.size(); i++) {
		easy[i] += easy[i-1];
	}
	
	LL answer = 0;
	for (int rem = 0; rem < m; rem++) {
		multiset<LL> future{0LL};
		for (int i = 0; i < (int) pref.size(); i++) {
			future.insert(pref[i][rem]);
		}
		LL so_far = 0;
		LL best_diff = LONG_LONG_MAX / 2;
		for (int last = -1; last < (int) pref.size(); last++) {
			if (last != -1) {
				so_far += pref[last].back();
				future.erase(future.find(pref[last][rem]));
				best_diff = min(best_diff, pref[last].back() - pref[last][rem]);
			}
			
			// 1) prefix of fulls + best in remaining suffix (future)
			int used = (last + 1) * m + rem;
			if (used <= k) {
				int more = k - used;
				if (more < (int) easy.size()) {
					LL maybe = so_far + *future.rbegin() + easy[more];
					answer = max(answer, maybe);
				}
			}
			
			// 2) prefix of fulls, with one replaced
			if (last != -1) {
				used = last * m + rem;
				if (used <= k) {
					int more = k - used;
					if (more < (int) easy.size()) {
						LL maybe = so_far - best_diff + easy[more];
						answer = max(answer, maybe);
					}
				}
			}
			
		}
	}
	cout << answer << endl;
}