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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

const int INF = -1e18;

signed main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);

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

    vector<int>A;
    vector<pair<int,vector<int>>>B;

    for(int i = 0; n>i; i++){
        vector<int>a(m);
        for(int j = 0; m>j; j++) cin>>a[j];
        if(m == 1 or a[0] >= a[m - 1]){
            for(auto x : a) A.push_back(x);
        }else{
            int sum = 0;
            vector<int>pref_a(m+1, 0);
            for(int j = 0; m>j; j++){
                sum += a[j];
                pref_a[j+1] = pref_a[j] + a[j];
            }
            B.push_back({sum, pref_a});
        }
    }
    sort(A.rbegin(), A.rend());
    vector<int> prefA(A.size() + 1, 0);
    for(int i = 0; A.size()>i; i++){
        prefA[i + 1] = prefA[i] + A[i];
    }
    sort(B.rbegin(), B.rend());
    int n1 = B.size();
    vector<int>pref(n1 + 1, 0);
    for(int i = 0; n1>i; i++){
        pref[i+1] = pref[i] + B[i].first;
    }
    vector<int>max_A(k + 1, INF);
    for(int f = 0; f <= n1; f++){
        int y = f * m;
        if(y <= k) max_A[y] = max(max_A[y], pref[f]);
    }
    for(int p=1; m>p; p++){
        vector<int>maxi(n1 + 1, INF);
        for(int i=1; n1>=i; i++){
            int downgrade_cost = B[i - 1].second[p] - B[i - 1].first;
            maxi[i] = max(maxi[i - 1], downgrade_cost);
        }

        vector<int>maxi_part(n1 + 2, INF);
        for(int i = n1; i >= 1; i--){
            maxi_part[i] = max(maxi_part[i + 1], B[i - 1].second[p]);
        }

        for(int f=0; n1>=f; f++){
            int y = f * m + p;
            if(y > k) continue;
            int best = INF;
            if(f + 1 <= n1){
                best = max(best, pref[f + 1] + maxi[f + 1]);
            }
            if(f < n1){
                best = max(best, pref[f] + maxi_part[f + 1]);
            }
            if(best != INF){
                max_A[y] = max(max_A[y], best);
            }
        }
    }
    int ans = 0;
    for(int i = 0; k >= i; i++){
        if(max_A[i] != INF){
            int rem = k - i;
            if(rem >= 0 and rem <= A.size()){
                ans = max(ans, max_A[i] + prefA[rem]);
            }
        }
    }
    cout << ans << "\n";
}