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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <cctype>
#include <string>
#include <vector>
#include <sstream>
#include <iterator>
#include <numeric>
#include <cmath>
using namespace std;

typedef vector <int > VI;
typedef vector < VI > VVI;
typedef long long LL;
typedef vector < LL > VLL;
typedef vector < double > VD;
typedef vector < string > VS;
typedef pair<int,int> PII;
typedef vector <PII> VPII;
typedef istringstream ISS;

#define ALL(x) x.begin(),x.end()
#define REP(i,n) for (int i=0; i<(n); ++i)
#define FOR(var,pocz,koniec) for (int var=(pocz); var<=(koniec); ++var)
#define FORD(var,pocz,koniec) for (int var=(pocz); var>=(koniec); --var)
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)
#define PB push_back
#define PF push_front
#define MP(a,b) make_pair(a,b)
#define ST first
#define ND second
#define SIZE(x) (int)x.size()

vector<LL> desc;
vector<VLL> inc;
vector<LL> sumy;
vector<pair<LL, int> > s_inc;
vector<LL> ss_inc;
vector<int> where;

int n_inc, n_dec;
int m;

int main(){
	int n, k;
	VLL t;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; ++i){
		t.clear();
		int czy = 0;
		for (int j = 0; j < m; ++j){
			long long x; scanf("%lld", &x);
			t.PB(x);
			if (j > 0 && x > t[j-1]) czy = 1;
		}
		if (czy) inc.PB(t);
		else {
			for (int j = 0; j < m; ++j) desc.PB(t[j]);
		}
	}
	sort(desc.begin(), desc.end());
	reverse(desc.begin(), desc.end());
	n_inc = SIZE(inc);
	while (SIZE(desc) < k) desc.PB(0);
	n_dec = SIZE(desc);
	sumy.PB(0LL);
	FOREACH(it, desc) sumy.PB(sumy.back() + *it);
	REP(i, n_inc) {
		LL s = 0LL;
		FOREACH(it2, inc[i]) s += *it2;
		s_inc.PB(MP(-s, i));
	}
	sort(ALL(s_inc));
	where.resize(n_inc);
	ss_inc.PB(0LL);
	REP(i, n_inc) {
	  ss_inc.PB(ss_inc.back() - s_inc[i].ST);
	  where[s_inc[i].ND] = i;
	}
	ss_inc.PB(ss_inc.back());
	
	long long best = sumy[k];
	for (int i = 0; i < n_inc; ++i) {
		long long loc_suma = 0LL;
		for (int j = 0; j < m; ++j) {
			// zjesc z i-tego inc stosu pierwsze j+1 nalesnikow, poza tym zachlan
			loc_suma += inc[i][j];
			int poz = k - (j + 1);
			int le = 0, ri = poz/m + 1; 
			while (le + 1 < ri) {
				int c = (le + ri)/2;
				long long akt = loc_suma;
				if (where[i] < c) {
					akt += ss_inc[c + 1] + s_inc[where[i]].ST;
				} else {
					akt += ss_inc[c];
				}
				long long koszt = sumy[k] - sumy[k - (c * m + j + 1)];
				if (akt <= koszt) ri = c;
				else le = c;
			}
			int c = le;
			long long akt = loc_suma;
			if (where[i] < c) {
				akt += ss_inc[c + 1] + s_inc[where[i]].ST;
			} else {
				akt += ss_inc[c];
			}
			long long wyn = sumy[k - (c * m + j + 1)] + akt;
			if (wyn > best) best = wyn;
		}
	}
	cout << best << endl;
	return 0;
}