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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int ll;


vector<ll> sort_downward(vector<vector<ll>> &stacks) {

    vector<ll> prefix_sum;
    for(auto &vec : stacks){
        for(auto x : vec){
            prefix_sum.push_back(x);
        }
    }

    sort(prefix_sum.begin(), prefix_sum.end());
    reverse(prefix_sum.begin(), prefix_sum.end());

    for(size_t i = 1; i < prefix_sum.size(); i++){
        prefix_sum[i] += prefix_sum[i-1];
    }

    return prefix_sum;
}


pair<vector<ll>, vector<vector<ll>>> rearange(vector<vector<ll>> &stacks){

    vector<ll> stack_sum(stacks.size(), 0);
    for(size_t i = 0; i < stacks.size(); i++){
        for(size_t j = 0; j < stacks[i].size(); j++){
            stack_sum[i] += stacks[i][j];
        }
    }

    std::vector<int> indices(stack_sum.size());
    for (size_t i = 0; i < stack_sum.size(); i++) {
        indices[i] = int(i);
    }

    std::sort(indices.begin(), indices.end(),
              [&stack_sum](int i1, int i2) {
                  return stack_sum[i1] > stack_sum[i2];
              });

    vector<ll> stack_sum_rearanged(stacks.size(), 0);
    vector<vector<ll>> stacks_rearanged(stacks.size());

    for(size_t i = 0; i < stack_sum.size(); i++){
        stack_sum_rearanged[i] = stack_sum[indices[i]];
        stacks_rearanged[i] = stacks[indices[i]];
    }

    return {stack_sum_rearanged, stacks_rearanged};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;

    cin >> n >> m >> k;

    vector<vector<ll>> upward;
    vector<vector<ll>> downward;

    for(int i = 0; i < n; i++){
        vector<ll> pancakes;
        for(int j = 0; j < m; j++){
            ll pancake;
            cin >> pancake;
            pancakes.push_back(pancake);
        }

        if(pancakes[0] >= pancakes.back()) downward.push_back(pancakes);
        else upward.push_back(pancakes);
        
    }

    vector<ll> prefix_sum = sort_downward(downward);
    if(upward.size() == 0){
        cout << prefix_sum[k-1] << endl;
        return 0;
    }

    auto [stack_sum, stacks] = rearange(upward);


    vector<vector<ll>> prefix_max(stacks.size(), vector<ll>(m, 0));

    prefix_max.back()[0] = stacks.back()[0];
    for(int j = 1; j < m; j++){
        prefix_max.back()[j] = stacks.back()[j] + prefix_max.back()[j-1];
    }

    for(int i = stacks.size() - 2; i >= 0; i--){
        ll prefix_sum = stacks[i][0];
        prefix_max[i][0] = max(prefix_sum, prefix_max[i+1][0]);

        for(int j = 1; j < m; j++){
            prefix_sum += stacks[i][j];
            prefix_max[i][j] = max(prefix_sum, prefix_max[i+1][j]);
        }
    }


    ll ans = 0;

    int stacks_taken = 0;
    ll sum_of_stacks = 0;

    while(stacks_taken < int(stack_sum.size()) && stacks_taken * m <= k){

        ll max_fill = -1;

        int rest = k - stacks_taken * m;
        
        if(rest > 0 && (int)prefix_sum.size() >= rest){
            max_fill = max(max_fill, prefix_sum[rest-1]);
        }

        for(int i = 0; i < min(m, rest); i++){
            int rest_up = rest - i - 1;

            if(rest_up == 0){
                max_fill = max(max_fill, prefix_max[stacks_taken][i]);
            }

            if(rest_up > 0 && (int)prefix_sum.size() >= rest_up){
                max_fill = max(max_fill, prefix_max[stacks_taken][i] + prefix_sum[rest_up-1]);
            }
        }

        if(max_fill >= 0){
            ans = max(ans, max_fill + sum_of_stacks);
        }

        sum_of_stacks += stack_sum[stacks_taken];
        stacks_taken++;
    }

    cout << ans << endl;
    return 0;
}