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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>

const int MAXN = 3e5+5, INF = 1e18;
vector<vector<int>> asc,desc,pref;
int res_desc[MAXN], res_asc[MAXN];

void solve_desc(int n, int m, int k){
    set<pi> st;
    vector<int> v(desc.size(),1);
    for(int i=0;i<desc.size();i++) st.insert({desc[i][1],i});
    int so_far=1;
    while(!st.empty()){
        auto [val,index] = *st.rbegin();
        res_desc[so_far] = res_desc[so_far-1] + val;
        so_far++;
        st.erase({val,index});
        v[index]++;
        if(v[index] <= m) st.insert({desc[index][v[index]],index});
    }
    for(int i=so_far;i<=k;i++) res_desc[i] = res_desc[i-1];
}

void solve_asc(int n, int m, int k){
    vector<set<pi>> st(m+1);
    vector<int> smallest(m+1,INF);
    for(int i=0;i<pref.size();i++){
       for(int j=1;j<=m;j++){
            st[j].insert({pref[i][j],i});
       }
    }
    int sum=0;
    for(int i=1;i<=m*asc.size();i++){
       if(i%m==0){
            auto [val,index] = *st[m].rbegin();
            sum += val;
            res_asc[i] = sum;
            for(int j=1;j<=m;j++) {st[j].erase({pref[index][j],index}); smallest[j] = min(smallest[j], pref[index][m] - pref[index][j]);}
        }
        else{
            auto [val,index] = *st[i%m].rbegin();
            auto [val2, index2] = *st[m].rbegin();
            res_asc[i] = max(sum+val,sum-smallest[i%m]+val2);
        }
    }
    for(int i=1;i<=k;i++) {res_asc[i] = max(res_asc[i], res_asc[i-1]);}

}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m,k; cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        vector<int> v = {0};
        bool ascending=false;
        for(int i=1;i<=m;i++){
            int a; cin >> a;
            ascending |= (i>1 && a>v.back());
            v.push_back(a);
        }
        if(!ascending) desc.push_back(v);
        else{
            vector<int> p = {0};
            for(int i=1;i<v.size();i++) p.push_back(p.back() + v[i]);
            asc.push_back(v);
            pref.push_back(p);
        }
    }
    solve_desc(n,m,k);
    solve_asc(n,m,k);
    int ans=0;
    for(int i=0;i<=k;i++) ans = max(ans, res_asc[i] + res_desc[k-i]);
    cout << ans << '\n';
}