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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n, m, k;
vector<LL> sumz, sumd;
vector<LL> v;
vector<vector<LL>>mal, ros;
vector<pair<LL, vector<LL>>> w;


vector<LL> zachlan(){
	vector<LL> v;
	v.reserve(m*mal.size());
	for(auto &w : mal){
		v.insert(v.end(), w.begin(), w.end());
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	return v;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	
	for(int i=0; i<n; i++){
		vector<LL> a(m);
		LL z = 0;
		bool nierosnace = true;
		for(auto &x : a){
			cin>>x;
			if(z > x){
				nierosnace=false;
			}
			z = x;
		}
		if(!nierosnace){
			mal.push_back(a);
		}else{
			ros.push_back(a);
		}
	}
	v = zachlan();
	
	for(unsigned i=0; i<ros.size(); i++){
		LL suma = accumulate(ros[i].begin(), ros[i].end(), 0LL);
		vector<LL> tmp = {0};
		for(unsigned j=0; j<ros[i].size(); j++){
			tmp.push_back(ros[i][j] + tmp.back());
		}
		w.push_back({suma, tmp});
	}
	sort(w.begin(), w.end());
	reverse(w.begin(), w.end());
	
	sumz.resize(n*m+5);
	for(unsigned i=0; i<v.size(); i++){
		sumz[i+1] = sumz[i] + v[i];
	}
	sumd.resize(n*m+5);
	for(unsigned i=0; i<w.size(); i++){
		sumd[(i+1)*m] = w[i].first + sumd[i*m];
	}
	vector<LL> dupa = {0};
	for(auto &[x, v] : w){
		dupa.push_back(dupa.back() + x);
	}
	dupa.push_back(-(1LL << 60));
	for(int i=1; i<=m; i++){
		if(w.empty())break;
		vector<LL> najwiekszy_zysk(w.size()+1);
		vector<LL> najmniejsza_strata(w.size()+1);
		najmniejsza_strata[0] = w[0].first - w[0].second[i];
		
		for(unsigned j=1; j<w.size(); j++){
			najmniejsza_strata[j] = min(najmniejsza_strata[j-1], w[j].first - w[j].second[i]);
		}
		najwiekszy_zysk[w.size()-1] = w.back().second[i];
		for(int j=(int)w.size()-2; j>=0; j--){
			najwiekszy_zysk[j] = max(najwiekszy_zysk[j+1], w[j].second[i]);
		}
		najwiekszy_zysk[w.size()] = (-(1LL << 60));
		najmniejsza_strata[w.size()] = (1e9);
		sumd[i] = najwiekszy_zysk[0];
		for(unsigned j=0; j<w.size(); j++){
			LL A = dupa[j+1] + najwiekszy_zysk[j+1];
			LL B = dupa[j+2] - najmniejsza_strata[j+1];
			if((j+1)*m+i >= (LL)sumd.size())continue;
			sumd[(j+1)*m+i] = max(A, B);
			
		}
	}
	
	LL res = 0;
	
	for(int i=0; i<=k; i++){
		int d = k-i;
		res = max(res, sumz[i]+sumd[d]);
	}

	
	cout<<res<<"\n";
	return 0;
}