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

int const N = 3e5+5;
int n, m, k;
ll res, pfx_pool[N], pfx_stacks[N];
vector <ll> pool;
vector <vector<ll>> a;
vector <pair<vector<ll>,ll>> stacks;
vector <vector<ll>> sfx, strata;
pair <ll, ll> ans[N];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < n; ++i){
        vector <ll> temp(m); for(ll &x : temp) cin >> x;
        bool ok = true;
        for(int i = 0; i < m-1; ++i) ok &= (temp[i] >= temp[i+1]);
        a.push_back(temp);
        if(m == 1 || ok){
            for(ll &x : temp) pool.push_back(x);
            continue;
        }
        vector <ll> pfx = temp;
        for(int i = 1; i < m; ++i) pfx[i] += pfx[i-1];
        stacks.push_back({pfx, pfx[m-1]});
    }
    sort(pool.begin(), pool.end(), [&](const ll& a, const ll& b){
        return a > b;
    });
    for(int i = 0; i < (int)pool.size(); ++i) pfx_pool[i] = pool[i] + (i == 0 ? 0 : pfx_pool[i-1]);
    sort(stacks.begin(), stacks.end(), [&](const pair<vector<ll>,ll>& a, const pair<vector<ll>,ll>& b){
        return a.second > b.second;
    });
    for(int i = 0; i < (int)stacks.size(); ++i) pfx_stacks[i] = stacks[i].second + (i == 0 ? 0 : pfx_stacks[i-1]);
    for(int i = (int)stacks.size()-1; ~i; --i){
        vector <ll> temp = stacks[i].first;
        if(sfx.empty()){
            sfx.push_back(temp);
            continue;
        }
        for(int j = 0; j < m; ++j) temp[j] = max(temp[j], sfx[sfx.size()-1][j]);
        sfx.push_back(temp);
    }
    for(int i = 0; i < (int)stacks.size(); ++i){
        vector <ll> temp(m+1, 0);
        temp[m] = stacks[i].second;
        for(int j = m-1; j; --j) temp[j] = (stacks[i].second - stacks[i].first[j-1]); 
        temp[0] = stacks[i].second;
        if(strata.empty()){
            strata.push_back(temp);
            continue;
        }
        for(int j = m-1; ~j; --j) temp[j] = min(temp[j], strata[i-1][j]);
        strata.push_back(temp);
    }
    reverse(sfx.begin(), sfx.end());
    for(int i = 1; i <= k; ++i){
        int full = min(i / m, (int)stacks.size());
        int rest = min(i - (full * m), m);
        ll ans1 = (full == 0 ? 0 : pfx_stacks[full-1]);
        ll ans2 = (full >= sfx.size() || rest <= 0) ? 0 : sfx[full][rest-1];
        ll ans3 = (full <= 0 || rest < 0 ? 0 : strata[full-1][rest]);
        ans[i].first = max(ans1 + ans2, full == 0 ? 0 : pfx_stacks[full] - ans3);
    }
    for(int i = 1; i <= k; ++i) ans[i].second = pfx_pool[i-1];
    for(int i = 0; i <= k; ++i){
        res = max(res, ans[i].first + ans[k-i].second);
    } 
    cout << res << '\n';
}