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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
#define e using u=ostream;template<class a,class b>u&operator<<(u&o,pair<a,b>&x)
using namespace std;e;u&operator<<(u&o,string&s){return o<<s.c_str();}template<
class t>auto operator<<(u&o,t&x)->decltype(x.end(),o){o<<'{';int i=2;for(auto y:
x)o<<", "+i<<y,i=0;return o<<'}';}e{return o<<'('<<x.first<<", "<<x.second<<')';}
#ifdef DEBUG
#define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define LOG(...)
#endif
#define ff first
#define ss second
#define ll long long

int n, m, k;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	vector <vector <ll> > v;
	vector <ll> free;
	for (int i = 0; i < n; i++) {
		vector <ll> s(m);
		vector <ll> pref(m);
		for (int j = 0; j < m; j++) {
			cin >> s[j];
			pref[j] = s[j];
			if (j > 0)
				pref[j] += pref[j-1];
		}
		if (s[0] < s[m-1]) {
			v.emplace_back(pref);
		}
		else {
			for (auto j : s)
				free.emplace_back(j);
		}
	}

	sort(v.begin(), v.end(), [&](auto a, auto b){
		return a[m-1] > b[m-1];
	});
	sort(free.rbegin(), free.rend());

	int nr = (int)v.size();
	int a = m*nr;
	int b = (int)free.size();
	LOG(a, b, nr);
	LOG(free);
	LOG(v);

	
	vector <ll> preffree(b+1);
	for (int i = 1; i <= b; i++) {
		preffree[i] = preffree[i-1] + free[i-1];
	}

	vector <ll> prefstos(nr+2);
	for (int i = 1; i <= nr; i++) {
		prefstos[i] = prefstos[i-1] + v[i-1][m-1];
	}

	const ll INF = (1LL << 60);
	
	vector <vector <ll> > pref(m, vector <ll> (nr+1, -INF));
	pref[0][0] = -INF;
	for (int j = 1; j <= nr; j++)
		pref[0][j] = max(pref[0][j-1], -v[j-1][m-1]);
	
	for (int i = 1; i < m; i++) {
		pref[i][0] = -INF;
		for (int j = 1; j <= nr; j++) {
			pref[i][j] = max(pref[i][j-1], v[j-1][i-1] - v[j-1][m-1]);
		}
	}
	
	vector <vector <ll> > suf(m, vector <ll> (nr+1, -INF));
	for (int j = 0; j <= nr; j++)
		suf[0][j] = 0;
	
	for (int i = 1; i < m; i++) {
		suf[i][nr] = -INF;
		for (int j = nr-1; j >= 0; j--) {
			suf[i][j] = max(suf[i][j+1], v[j][i-1]);
		}
	}	
		
	LOG(preffree);
	LOG(prefstos);
	LOG(pref);
	LOG(suf);

	ll res = 0;
	for (int i = 0; i <= k; i++) {
		LOG(i, k, k-i);
		if (i > a)
			continue;
		if (k - i > b)
			continue;
		int x = i / m;
		int y = i % m;
		LOG(x, y);
		ll stosy = prefstos[x] + suf[y][x];
		if (x < nr)
			stosy = max(stosy, prefstos[x+1] + pref[y][x+1]);
		ll f = preffree[k-i];
		LOG(stosy, f);
		res = max(res, stosy+f);
	}
	cout << res << "\n";
}