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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef vector<LL> VI;

struct IncStack
{
	LL total = 0;
	VI pref;
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	VI a(m), decVals;
	decVals.reserve(n * m);
	vector<IncStack> inc;
	inc.reserve(n);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j) cin >> a[j];
		bool rosnacy = a.front() <= a.back();
		if (rosnacy)
		{
			IncStack s;
			s.pref.assign(m, 0);

			LL sum = 0;
			for (int j = 0; j < m; ++j)
			{
				sum += a[j];
				if (j + 1 < m) s.pref[j + 1] = sum;;
			}
			s.total = sum;
			inc.push_back(move(s));
		}
		else for (int j = 0; j < m; ++j) decVals.push_back(a[j]);
	}

	sort(decVals.begin(), decVals.end(), greater<LL>());
	int D = (int)decVals.size();
	VI decPref(D + 1, 0);
	for (int i = 0; i < D; ++i) decPref[i + 1] = decPref[i] + decVals[i];

	sort(inc.begin(), inc.end(), [](const IncStack& a, const IncStack& b) { return a.total > b.total; });
	int ic = (int)inc.size();
	VI totalPref(ic + 1, 0);
	for (int i = 0; i < ic; ++i) totalPref[i + 1] = totalPref[i] + inc[i].total;

	const LL NEG = (LL)-4e18;
	LL ans = NEG;

	for (int f = 0; f <= ic; ++f)
	{
		LL used = 1LL * f * m;
		if (used > k) break;

		int rem = k - used;
		if (rem <= D) ans = max(ans, totalPref[f] + decPref[rem]);
	}

	if (m >= 2 && ic > 0)
	{
		VI suf(ic + 1), pref(ic);
		for (int t = 1; t < m; ++t)
		{
			suf[ic] = NEG;
			for (int i = ic - 1; i >= 0; --i) suf[i] = max(suf[i + 1], inc[i].pref[t]);
			LL best = NEG;
			for (int i = 0; i < ic; ++i)
			{
				best = max(best, inc[i].pref[t] - inc[i].total);
				pref[i] = best;
			}

			for (int f = 0; f <= ic; ++f)
			{
				LL used = 1LL * f * m + t;
				if (used > k) break;

				int rem = k - used;
				if (rem > D) continue;

				LL bestInc = NEG;
				if (f < ic && suf[f] != NEG) bestInc = max(bestInc, totalPref[f] + suf[f]);
				if (f >= 1 && f + 1 <= ic && pref[f - 1] != NEG) bestInc = max(bestInc, totalPref[f + 1] + pref[f - 1]);
				if (bestInc != NEG) ans = max(ans, bestInc + decPref[rem]);
			}
		}
	}

	cout << ans << endl;
	return 0;
}