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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

bool ok(vector<ll> a) { // czy nie malejąca
	for(ll i=1; i<a.size(); ++i) if(a[i] < a[i-1]) return false;
	return true;
}

vector<ll> solve1(vector<vector<ll>> A, ll k) {
	ll n = A.size();
	vector<ll> res(k+1);
	if(!n) return res;
	ll m = A[0].size();

	vector<vector<ll>> prefix(n, vector<ll>(m+1));
	for(ll i=0; i<n; ++i) {
		for(ll j=1; j<=m; ++j) {
			prefix[i][j] = prefix[i][j-1] + A[i][j-1];
		}
	}
	vector<vector<pair<ll, ll>>> best(m+1);
	for(ll i=1; i<=m; ++i) {
		for(ll j=0; j<n; ++j) best[i].push_back({prefix[j][i], j});
		sort(best[i].begin(), best[i].end());
		reverse(best[i].begin(), best[i].end());
	}
	vector<priority_queue<ll>> prio(m+1);
	vector<ll> idx(m+1);
	vector<ll> used(n);
	ll cnt = 0;
	ll ans = 0;
	for(ll i=1; i<=k; ++i) {
		res[i] = res[i-1];
		if(cnt == n) continue;
		if(i%m) {
			ll x = i%m;
			while(idx[m] < n && used[best[m][idx[m]].second]) idx[m]++;
			while(idx[x] < n && used[best[x][idx[x]].second]) idx[x]++;
			res[i] = ans + best[x][idx[x]].first;

			if(cnt > 0) {
				ll cand = ans + best[m][idx[m]].first + prio[x].top();
				res[i] = max(res[i], cand);
			}
		} else {
			while(idx[m] < n && used[best[m][idx[m]].second]) idx[m]++;
			ans += best[m][idx[m]].first;
			res[i] = ans;
			used[best[m][idx[m]].second] = 1;
			res[i] = ans;
			cnt++;
			for(ll j=1; j<=m; ++j) prio[j].push(-prefix[best[m][idx[m]].second][m] + prefix[best[m][idx[m]].second][j]);
		}
	}
	return res;
}

vector<ll> solve2(vector<vector<ll>> b, ll k) {
	vector<ll> res(k+1);
	priority_queue<ll> pq;
	for(auto y : b) for(auto x : y) pq.push(x);
	for(ll i=1; i<=k; ++i) {
		if(pq.empty()) res[i] = res[i-1];
		else {
			res[i] = res[i-1] + pq.top();
			pq.pop();
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n, m, k;
	cin >> n >> m >> k;
	vector<vector<ll>> b1, b2;
	for(ll i=0; i<n; ++i) {
		vector<ll> a(m);
		for(auto &x : a) cin >> x;
		if(ok(a)) {
			b1.push_back(a);
		} else {
			b2.push_back(a);
		}
	}
	vector<ll> ans2 = solve2(b2,k);
	vector<ll> ans1 = solve1(b1,k);
	ll res = 0;
	for(ll i=0; i<=k; ++i) res = max(res, ans2[i] + ans1[k-i]);
	cout << res << '\n';

	return 0;
}