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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    

    vector<vector<long long>> pref;//(n, vector<long long>(m+1));
    vector<long long> full;
	vector<long long> desc;
	int nasc = 0;
	
    for (int i = 0; i < n; i++) {
        vector<long long> a(m);
        bool dsc = true;
        for (int j = 0; j < m; j++) {
        	cin >> a[j];
        	if (j>0 && a[j]>a[j-1])
        		dsc = false; 
        }
		if (dsc) {
			for (auto v : a) 
				desc.push_back(v);
		} else {
			pref.push_back(vector<long long>(m+1));
	        pref[nasc][0] = 0;
	        for (int t = 1; t <= m; t++)
	            pref[nasc][t] = pref[nasc][t-1] + a[t-1];
	
	        full.push_back(pref[nasc][m]);
	        //cout << full[nasc]<<endl;
	        nasc++;
		}
    }
	
	sort(desc.begin(), desc.end(), greater<>());
	
	vector<long long> sdesc(desc.size()+1,0);
	partial_sum(desc.begin(), desc.end(),sdesc.begin()+1);
	//for (auto v:sdesc) cout << v <<" "; cout << endl;

    vector<int> ord(nasc);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){
        return full[a] > full[b];
    });
	// for (int idx : ord) {
 //       cout << "Stos " << idx << " (suma = " << full[idx] << "): ";
 //       for (long long v : pref[idx]) cout << v << " ";
 //       cout << "\n";
 //   }

    int K = nasc * m;
    vector<long long> best(K+1);

    long long sumFull = 0;
    for (int i = 0; i < nasc; i++)
        sumFull += full[ord[i]];

    vector<multiset<long long, greater<long long>>> bestPrefix(m+1);

    int kk = K;
    best[kk] = sumFull;

    // Skracamy stosy od najgorszego
    for (int idx = nasc-1; idx >= 0; idx--) {
        int s = ord[idx];
        sumFull -= full[s];
        //cout << sumFull << endl;
        // Skracamy stos od m do 0
        for (int len = m-1; len >= 0; len--) {
        	kk--;
            if (len >= 0) {

                bestPrefix[len].insert(pref[s][len]);

                // Wynik dla k:
                long long add = 0;
                if (!bestPrefix[len].empty())
                    add = *bestPrefix[len].begin(); // największy prefix tej długości

                best[kk] = sumFull + add;
                //cout << kk << " " << best[kk] <<endl;
            } 
        }
    }
    
    
	long long ans = 0;
	
    //for (int i = 0; i <= K; i++) cout << best[i] << " "; cout << endl;
   
    
    for (int i=0; i<=k; i++) {
    	int r = k-i;
    	if (r>=sdesc.size()) continue;
    	if (i>K || r<0)
    		break;
    	long long b = best[i]+sdesc[r];
    	//cout << "! " << i << "," << r << "=" << b << endl;
    	if (b>ans)
    		ans = b;
    	
    }
    
    cout << ans;
    
}