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
//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define rep(n) for (ll i = 0 ; i<n ; i++)
#define pb push_back

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	ll n,m,k;
	cin >> n >> m >> k;
	vector<vector<ll>> asc;
	vector<vector<ll>> desc;
	if (m==1){
		ll xd[n];
		rep(n) cin >> xd[i];
		sort(xd,xd+n);
		ll w = 0;
		for (ll i = n-1 ; i>=n-k ; i--) w+=xd[i];
		cout << w << '\n';
		return 0;
	}
	vector<ll> a(m);
	rep(n){
		for (ll j = 0 ; j<m ; j++){
			cin >> a[j];
		}
		if (a[0]<a[m-1]) asc.pb(a);
		else desc.pb(a);
	}
	ll wa[n*m+1] = {0};
	ll wd[n*m+1] = {0};
	ll ktory[desc.size()] = {0};
	priority_queue<pair<ll,ll>> q;
	rep(desc.size()) q.push({desc[i][0],i});
	ll c = 1;
	while (q.size()){
		ll x = q.top().first;
		ll i = q.top().second;
		q.pop();
		wd[c] = wd[c-1]+x;
		c++;
		ktory[i]++;
		if (ktory[i]==m) continue;
		q.push({desc[i][ktory[i]],i});
	}
	ll pref[asc.size()][m+1];
	priority_queue<pair<ll,ll>> best[m+1];
	priority_queue<ll> funnycase[m+1];
	bool taken[asc.size()] = {0};
	rep(asc.size()){
		pref[i][0] = 0;
		for (ll j = 1 ; j<=m ; j++){
			pref[i][j] = pref[i][j-1]+asc[i][j-1];
			best[j].push({pref[i][j],i});
		}
	}
	ll stala = 0;
	for (c = 1 ; c<=m*asc.size() ; c++){
		ll ind = (c-1)%m+1;
		while (taken[best[ind].top().second]) best[ind].pop();
		wa[c] = best[ind].top().first+stala;
		if (c%m==0){
			taken[best[ind].top().second] = 1;
			for (ll j = 1 ; j<=m ; j++){
				funnycase[j].push(pref[best[ind].top().second][j]-best[ind].top().first);
			}
			stala+=best[ind].top().first;
			while (best[ind].size() && taken[best[ind].top().second]) best[ind].pop();
		}else if (funnycase[ind].size()){
			wa[c] = max(wa[c],best[m].top().first+stala+funnycase[ind].top());
		}
	}
	ll w = 0;
	for (ll i = 0 ; i<=k ; i++){
		w = max(w,wa[i]+wd[k-i]);
	}
	cout << w << '\n';
}