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

typedef pair<long long, long long> par;
vector<long long> tab, decel, isdec;
vector<vector<long long> > v;
vector<par> stacks;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    long long n, m, k, a, b, c, d, e, f, st, wyn = 0, x = 0;
    cin>>n>>m>>k;
    tab.resize(n+1, 0);
    isdec.resize(n+1, 1);
    v.resize(n+1);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a;
            v[i].push_back(a);
            tab[i] += a;
        }
        for(int j=1; j<m; j++) if(v[i][j-1] < v[i][j]) isdec[i] = 0;
        if(isdec[i]) {
            for(int j=0; j<m; j++) decel.push_back(v[i][j]);
        }
        else stacks.push_back({tab[i], i});
    }
    sort(decel.begin(), decel.end());
    sort(stacks.begin(), stacks.end());
    
    a = 0;
    b = decel.size() - 1;
    st = stacks.size() - 1;
    if(decel.size() > 0) {
        for(int i=b; i>b-m; i--) a += decel[i];
    }
    while(k >= m) {
        if(st < 0 || stacks[st].first < a) {
            wyn += a;
            b -= m;
            a = 0;
            if(b >= 0) {
                for(int i=0; i<m; i++) a += decel[b-i];
            }
        }
        else {
            wyn += stacks[st].first;
            st--;
        }
        k -= m;
    }

    if(k > 0) {
        a = d = wyn;
        if(b >= 0) {
            for(int i=0; i<k; i++) a += decel[b-i];
        }
        if(st >= 0) {
            c = stacks[st].second;
            e = 0;
            for(int i=0; i<k; i++) d += v[c][i];
            for(int i=k; i<m; i++) e += v[c][i];
            for(int i=st+1; i<stacks.size(); i++) {
                c = stacks[i].second;
                f = 0;
                for(int j=k; j<m; j++) f += v[c][j];
                if(e > f) {
                    d = d + e - f;
                    swap(e, f);
                }
            }
            if(b < (int)decel.size() - 1) {
                f = 0;
                for(int i=1; i<=m-k; i++) f += decel[b+i];
                if(e > f) {
                    d = d + e - f;
                    swap(e, f);
                    x = 1;
                }
            }
        }
        if(a > d) {
			wyn = a;
			b -= k;
		}
        else {
			wyn = d;
			if(x) b += (m-k);
			x = 2;
		}
    }
	
	if(k == 0 && st >= 0) {
		c = stacks[st].second;
		for(int i=0; i<m; i++) {
			if(b == decel.size() - 1) break;
			if(v[c][i] >= decel[b+1]) {
				wyn = wyn - decel[b+1] + v[c][i];
				b++;
			}
			else break;
		}
	}
    cout<<wyn;
    return 0;
}