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>
using namespace std;

long long n, m, k;

struct Inc {
	vector<long long> a;
	long long s;
};

bool cmp(const Inc &a, const Inc &b) {
	return a.s > b.s;
}

vector<Inc> inc;
vector<long long> tp;
vector<long long> tpp;
vector<long long> pinc;
vector<long long> a;
long long wyn = 0;

long long getint() {
	long long nm;
	char c = getchar_unlocked();
	while (c<'0' or c>'9') c = getchar_unlocked();
	nm = c - '0';
	c = getchar_unlocked();
	while (c >= '0' and c <= '9') {
		nm *= 10;
		nm += (c - '0');
		c = getchar_unlocked();
	}
	return nm;
}


int main() {
	n = getint();
	m = getint();
	k = getint();
	for (int i = 0; i < n; i++) {
		int bul = 0; // czy inc;
		a.clear();
		a.push_back(0);
		for (int j = 0; j < m; j++) {
			long long b;
			b = getint();
			a.push_back(b);
			if (a.size() >= 3 and a[a.size() - 2] < a[a.size() - 1]) bul = 1;
		}

		if (bul) { //inc
			long long sm = 0;
			for (int i = 0; i < a.size(); i++) {
				sm += a[i];
				if (i > 0)a[i] += a[i - 1];
			}
			inc.push_back({a, sm});

		}

		else { //dec
			for (int j = 1; j < a.size(); j++) tp.push_back(a[j]);
		}
	}

	sort(tp.rbegin(), tp.rend());
	tpp.push_back(0);

	for (auto i : tp) tpp.push_back(tpp.back() + i);

	sort(inc.begin(), inc.end(), cmp);
	pinc.resize(inc.size() + 1, 0);

	for (int i = 1; i <= inc.size(); i++) {
		pinc[i] = pinc[i - 1] + inc[i - 1].s;
	}

	long long siz = inc.size();

	vector<vector<long long>> suf(m, vector<long long>(siz + 2, LLONG_MAX));
	vector<vector<long long>> pref(m, vector<long long>(siz + 2, 0));

	for (int i = 0; i < m; i++) {
		for (int j = 1; j <= siz; j++) {
			suf[i][j] = min(suf[i][j - 1], inc[j - 1].s - inc[j - 1].a[i]);
		}

		for (int j = siz; j >= 1; j--) {
			pref[i][j] = max(pref[i][j + 1], inc[j - 1].a[i]);
		}
	}


	for (int j = 0; j <= siz; j++) {
		for (int i = 0; i < m and j * m + i <= k; i++) {
			long long twyn = pinc[j];

			if (i > 0 and j < siz) {
				twyn = max(twyn, pinc[j] + pref[i][j + 1]);
				if (j > 0) twyn = max(twyn, pinc[j + 1] - suf[i][j]);
			}


			if (0 <= (k - (j * m + i)) and (k - (j * m + i)) < tpp.size()) {
				wyn = max(wyn, twyn + tpp[k - (j * m + i)]);
			}

		}
	}

	cout << wyn << '\n';
}