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 <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) (int)(x).size()
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define REP(x, n) for (int x = 0; x < (n); x++)
#define FOR(x, b, e) for (int x = (b); x <= (e); x++)
#define FORD(x, b, e) for (int x = (b); x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)

typedef long long int LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int MXN = 300010;
const int C = 262144;
const int MOD = 1000000007;
const LL INF = 1LL << 60;

int n, m, k;
LL mal[MXN];
int mal_ss;
vector<pair<LL, vector<LL>>> ros;
vector<LL> pref_sum_ros;

bool cmp(const pair<LL, vector<LL>> &a, const pair<LL, vector<LL>> &b) {
	return a.F > b.F;
}

LL suma_mal(int ile) {
	return min(ile, mal_ss) > 0 ? mal[min(ile, mal_ss) - 1] : 0;
}

LL best_ros(int x, int skip_index) {
	if(x == 0)
		return 0;
	if(skip_index == -1 || skip_index >= x)
		return pref_sum_ros[x - 1];
	return pref_sum_ros[min(x, SIZE(ros) - 1)] - ros[skip_index].F;
}

int max_pos(int skip_index, int nalesniki) {
	return min(max(0, SIZE(ros) - (skip_index >= 0)), nalesniki / m);
}

LL calc(int ile_rosnacych, int skip_index, int nalesniki, LL zjedzone) {
	return best_ros(ile_rosnacych, skip_index) + zjedzone + suma_mal(nalesniki - ile_rosnacych * m);
}

LL ternary_search(int skip_index, int nalesniki, LL zjedzone) {
	int R = max_pos(skip_index, nalesniki);
	LL res = -INF;
	int L = 0;
	while(R - L > 2) {
		int S1 = L + (R - L) / 3;
		int S2 = R - (R - L) / 3;
		LL val1 = calc(S1, skip_index, nalesniki, zjedzone);
		LL val2 = calc(S2, skip_index, nalesniki, zjedzone);
		if (val1 < val2)
			L = S1;
		else
			R = S2;
	}
	FOR(i, L, R)
		res = max(res, calc(i, skip_index, nalesniki, zjedzone));
	return res;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	FOR(i, 1, n) {
		vector<LL> stos;
		FOR(j, 1, m) {
			LL x;
			scanf("%lld", &x);
			stos.PB(x);
		}
		if(stos[0] < stos.back()) {
			LL sum = 0;
			vector<LL> pref_sum;
			pref_sum.PB(0);
			FOR(j, 0, SIZE(stos) - 1) {
				pref_sum.PB(stos[j] + sum);
				sum += stos[j];
			}
			ros.PB(MP(sum, pref_sum));
		} 
		else {
			FOR(j, 0, SIZE(stos) - 1)
				mal[mal_ss++] = stos[j];
		}
	}
	sort(mal, mal + mal_ss, greater<LL>());
	FOR(i, 1, mal_ss - 1)
		mal[i] += mal[i - 1];
	sort(ALL(ros), cmp);
	LL sum = 0;
	FOR(i, 0, SIZE(ros) - 1) {
		pref_sum_ros.PB(ros[i].F + sum);
		sum += ros[i].F;
	}
	LL res = ternary_search(-1, k, 0);
	FOR(q, 0, SIZE(ros) - 1)
		FOR(p, 0, min(k, m - 1))
			res = max(res, ternary_search(q, k - p, ros[q].S[p]));
	printf("%lld\n", res);
	return 0;
}