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>
#define F first
#define S second
#define pii pair<long long, long long>
using namespace std;
using ll = long long;
using ld = long double;

constexpr int SIZE = 3e5+5;
constexpr ll INF = 4e18;

vector<ll> seq[SIZE];
vector<ll> pref[SIZE];
vector<ll> bsuf[SIZE];
vector<ll> bpre[SIZE];
vector<ll> big;
vector<pii> best;

ll where[SIZE];
bool inc[SIZE];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

	ll n2 = n;

	ll a;

	for (int i=1; i<=n; i++){
		seq[i].push_back(0);
		for (int j=0; j<m; j++){
			cin >> a;
			seq[i].push_back(a);
		}
		if (seq[i][1] < seq[i][m]) inc[i] = 1;
		else n2 --;
	}

	for (int i=1; i<=n; i++){
		if (inc[i]) continue;
		for (int j=1; j<=m; j++) big.push_back(seq[i][j]);
	}


	big.push_back(INF);
	sort(big.begin(), big.end(), greater<>());
	big[0] = 0;

	

	ll sz = big.size()-1;

	for (int i=1; i<=sz; i++) big[i] += big[i-1];



	for (int i=1; i<=n; i++){
		if (!inc[i]) continue;

		pref[i].push_back(0);

		for (int j=1; j<=m; j++){
			pref[i].push_back(pref[i].back() + seq[i][j]);
		}

		best.push_back({pref[i][m], i});
	}

	best.push_back({INF, INF});
	sort(best.begin(), best.end(), greater<>());
	best[0] = {0, 0};


	for (int i=1; i<=n2; i++) best[i].F += best[i-1].F;
	for (int i=1; i<=n2; i++) where[best[i].S] = i;

	for (int i=0; i<m; i++) bsuf[n2+1].push_back(0);
	for (int t=n2; t; t--){
		bsuf[t].push_back(0);
		for (int r=1; r<m; r++){
			bsuf[t].push_back(max(bsuf[t+1][r], pref[best[t].S][r]));
		}
	}
	
	
	
	for (int i=0; i<m; i++) bpre[0].push_back(-INF);
	for (int t=1; t<=n2; t++){
		bpre[t].push_back(0);
		for (int r=1; r<m; r++){
			bpre[t].push_back(max(bpre[t-1][r], pref[best[t].S][r]-pref[best[t].S][m]));
		}
	}

	ll mxt = min(k/m, n2);
	ll mxr = min(k, m-1);

	ll ans = big[min(k, sz)];

	for (ll t=0; t<=mxt; t++){
		for (ll r=0; r<=mxr; r++){
			if (m*t+r > k || m*t+r+sz < k) continue;

			ll res;

			if (t == n2){
				res = best[t].F;
			}else {
				res = best[t].F + bsuf[t+1][r];
				if (r) res = max(res, best[t+1].F + bpre[t][r]);
			}
  
			ans = max(ans, res + big[k-t*m-r]);
		}
	}

	cout << ans;
	
return 0;}