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
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -1e18;

struct Ros {
	ll suma;
	vector<ll> pref;
};

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	ll n, m, k;
	cin >> n >> m >> k;

	vector<Ros> ros;
	vector<vector<ll>> mal;

	ros.reserve(n);
	mal.reserve(n);

	for (ll i = 0; i < n; ++i) {
		vector<ll> a(m);
		for (ll j = 0; j < m; ++j)
			cin >> a[j];

		if (a.front() < a.back()) {
			Ros st;
			st.pref.resize(m + 1);
			st.pref[0] = 0;
			for (ll j = 1; j <= m; ++j)
				st.pref[j] = st.pref[j - 1] + a[j - 1];
			st.suma = st.pref[m];
			ros.push_back(st);
		} else
			mal.push_back(a);
	}

	vector<ll> dpm(k + 1, NEG);
	dpm[0] = 0;

	priority_queue<pair<ll, ll>> pq;
	vector<ll> poz(mal.size(), 0);

	for (ll i = 0; i < (ll)mal.size(); ++i) {
		pq.push({mal[i][0], i});
	}

	for (ll i = 1; i <= k && !pq.empty(); ++i) {
		auto [w, id] = pq.top();
		pq.pop();

		dpm[i] = dpm[i - 1] + w;

		poz[id]++;
		if (poz[id] < (ll)mal[id].size())
			pq.push({mal[id][poz[id]], id});
	}

	sort(ros.begin(), ros.end(), [](const Ros &A, const Ros &B) {
		return A.suma > B.suma;
	});

	ll s = (ll)ros.size();
	vector<ll> suma(s + 1, 0);
	vector<ll> Pref(s + 1, 0);

	for (ll i = 1; i <= s; ++i) {
		suma[i] = ros[i - 1].suma;
		Pref[i] = Pref[i - 1] + suma[i];
	}

	vector<ll> dpr(k + 1, NEG);
	dpr[0] = 0;

	for (ll q = 0; q <= s; ++q) {
		ll t = q * m;
		if (t <= k)
			dpr[t] = max(dpr[t], Pref[q]);
	}

	vector<ll> lw(s + 1, NEG), pr(s + 2, NEG);

	for (ll r = 1; r < m; ++r) {
		fill(lw.begin(), lw.end(), NEG);
		fill(pr.begin(), pr.end(), NEG);

		for (ll i = 1; i <= s; ++i) {
			ll p = ros[i - 1].pref[r];
			lw[i] = max(lw[i - 1], p - suma[i]);
		}

		for (ll i = s; i >= 1; --i) {
			ll p = ros[i - 1].pref[r];
			pr[i] = max(pr[i + 1], p);
		}

		for (ll q = 0; q < s; ++q) {
			ll t = q * m + r;
			if (t > k)
				break;

			ll najl = NEG;

			if (pr[q + 1] != NEG)
				najl = max(najl, Pref[q] + pr[q + 1]);

			if (q >= 1 && lw[q] != NEG)
				najl = max(najl, Pref[q] + suma[q + 1] + lw[q]);

			dpr[t] = max(dpr[t], najl);
		}
	}

	ll wynik = 0;
	for (ll t = 0; t <= k; ++t) {
		if (dpr[t] == NEG || dpm[k - t] == NEG)
			continue;
		wynik = max(wynik, dpr[t] + dpm[k - t]);
	}

	cout << wynik << '\n';
}