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
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
using ll = long long;

vector<vector<ll>> asc;
vector<ll> desc;
vector<ll> prefix, block;

vector<ll> asc_res, desc_res;

bool decreasing(vector<ll> &v){
    for(int i=1; i<v.size()-1; i++){
        if(v[i] < v[i+1]) return true;
    }
    return false;
}

void calculate_res(int offset, int block_size, int n){
    priority_queue<pair<ll, int>> order;
    priority_queue<ll> seen;
    set<pair<ll, int>> not_seen;
    for(int i=0; i<n; i++){
        order.push({block[i], i});
        not_seen.insert({prefix[i], i});
    }
    seen.push(-(1ll<<60));
    ll sum = 0;
    for(int i=0; i<n; i++){
        ll res = max(seen.top()+order.top().first, prev(not_seen.end())->first) + sum;
        asc_res[i*block_size+offset] = res;
        auto [s, v] = order.top();
        order.pop();
        sum += s;
        not_seen.erase({prefix[v], v});
        seen.push(prefix[v] - block[v]);
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k;
    cin>>n>>m>>k;
    for(int i=0; i<n; i++){
        vector<ll> v(m+1, 0);
        for(int j=1; j<=m; j++){
            cin>>v[j];
        }
        if(m<2 || !decreasing(v)){
            for(auto j: v){
                desc.push_back(j);
            }
        }else{
            ll block_sum = 0;
            for(auto j: v){
                block_sum += j;
            }
            prefix.push_back(0);
            block.push_back(block_sum);
            asc.push_back(v);
        }
    }
    desc_res.assign(k+1, 0);
    asc_res.assign(n*m+1, 0);
    if(desc.size()){
        sort(desc.begin(), desc.end());
    }
    for(int i=1; i<=k; i++){
        if(desc.size()){
            desc_res[i] = desc_res[i-1] + desc.back();
            desc.pop_back();
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=0; j<asc.size(); j++){
            prefix[j] += asc[j][i];
        }
        calculate_res(i, m, asc.size());
    }
    /*for(int i=0; i<asc.size(); i++){
        for(int j=1; j<=m; j++){
            cerr<<asc_res[i*m+j]<<' ';
        }
        cerr<<nl;
    }*/
    ll res = 0;
    for(int i=0; i<=k; i++){
        res = max(asc_res[i]+desc_res[k-i], res);
    }
    cout<<res<<nl;
    return 0;
}