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

#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    vector<vll> increasing;
    vll decreasing;
    for (int i=0; i<n; i++) {
        vll tmp(m);
        for (ll& i : tmp) cin>>i;
        if (tmp[0] >= tmp.back()) for (ll i : tmp) decreasing.push_back(i);
        else increasing.push_back(tmp);
    }
        
    vector<vll> inc_sums(increasing.size());
    for (int i=0; i<increasing.size(); i++) {
        inc_sums[i].push_back(increasing[i][0]);
        for (int j=1; j<m; j++) inc_sums[i].push_back(inc_sums[i].back()+increasing[i][j]);
    }
    sort(all(decreasing), greater<ll>());

    vi incr_max(increasing.size());
    for (int i=0; i<incr_max.size(); i++) incr_max[i] = i;
    sort(all(incr_max), [&inc_sums](int a, int b) { return inc_sums[a].back() > inc_sums[b].back(); });
    vector<bool> visited_inc(increasing.size(),false);

    int tmp = k;
    ll res = 0;
    int taken_inc = 0;
    for (; taken_inc<incr_max.size(); taken_inc++) {
        if (tmp < m) break;
        res += inc_sums[incr_max[taken_inc]].back();
        visited_inc[incr_max[taken_inc]] = true;
        tmp -= m;
    }

    vll mx_sum(m,0);
    for (int i=0; i<m; i++) for (int j=0; j<increasing.size(); j++) if (!visited_inc[j]) mx_sum[i] = max(mx_sum[i], inc_sums[j][i]);

    int st = 0;
    if (increasing.size()*m > k) {
        if (tmp>0) res += mx_sum[tmp-1];
    } else {
        st = k-increasing.size()*m;
        for (int i=0; i<st; i++) res += decreasing[i];
        tmp = 0;
    }

    ll cur_sum = res;
    for (int i=st; i<k && i<decreasing.size(); i++) {
        if (tmp == 0) {
            taken_inc--;
            cur_sum -= inc_sums[incr_max[taken_inc]].back();
            visited_inc[incr_max[taken_inc]] = false;
            for (int j=0; j<mx_sum.size(); j++) mx_sum[j] = max(mx_sum[j], inc_sums[incr_max[taken_inc]][j]);

            tmp = m-1;
            if (tmp > 0) cur_sum += mx_sum[tmp-1];
        } else {
            cur_sum -= mx_sum[tmp-1];
            tmp--;
            if (tmp > 0) cur_sum += mx_sum[tmp-1];
        }

        cur_sum += decreasing[i];
        res = max(res, cur_sum);
    }

    cout<<res<<'\n';

    return 0;
}