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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pb push_back
#define F first 
#define S second
#define INF (ll)2e18
#define pii pair<int,int>
#define int ll

void solve() {

    int n,m,k; cin >> n >> m >> k;    
    vector<vector<int>> a(n,vector<int>(m));
    vector<int> sum(n);
    vector<int> iter(n);
    priority_queue<pii> pq;
    vector<int> perm;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
            sum[i] += a[i][j];
        }
        bool is_inc = false;
        for (int j = 1; j < m; j++){
            if (a[i][j] > a[i][j-1]){
                is_inc = true;
                break;
            }
        }
        if (!is_inc){
            pq.push({a[i][0],i});
        } else {
            perm.pb(i);
        }
    }
    vector<int> pref(n*m+1);
    int j = 1;
    while(!pq.empty()){
        auto [v,idx] = pq.top(); pq.pop();
        pref[j] = pref[j-1] + v;
        j++;
        iter[idx]++;
        if(iter[idx] < m){
            pq.push({a[idx][iter[idx]],idx});
        }
    }
    while(j <= n*m){
        pref[j] = pref[j-1];
        j++;
    }
    sort(all(perm), [&](const int a, const int b){return sum[a] > sum[b];});
    vector<vector<int>> max_suffix(perm.size(), vector<int>(m));
    vector<vector<int>> min_prefix_inverse(perm.size(), vector<int>(m,INF));
    for (int i = 0; i < perm.size(); i++){
        int pref_sum = 0;
        for (int j = 0; j < m; j++){
            if (i > 0){
                min_prefix_inverse[i][j] = min_prefix_inverse[i-1][j];
            }
            pref_sum += a[perm[i]][j];
            min_prefix_inverse[i][j] = min(min_prefix_inverse[i][j], sum[perm[i]] - pref_sum);
        }
    }
    for (int i = perm.size()-1; i >= 0; i--){
        int pref_sum = 0;
        for (int j = 0; j < m; j++){
            if (i < perm.size()-1){
                max_suffix[i][j] = max_suffix[i+1][j];
            }
            pref_sum += a[perm[i]][j];
            max_suffix[i][j] = max(max_suffix[i][j], pref_sum);
        }
    }
    int ans = pref[k];
    int pref_sum = 0;
    for (int i = 0; i < perm.size(); i++){
        if (i*m > k) break;
        pref_sum += sum[perm[i]];
        for (int j = 0; j < m; j++){
            if (i*m+j+1 > k) break;
            int cur = pref_sum - min_prefix_inverse[i][j];
            if (i+1 < perm.size()){
                cur = max(cur, pref_sum - sum[perm[i]] + max_suffix[i+1][j]);
            }
            ans = max(ans, cur + pref[k - (i*m+j+1)]);
        }
    }
    cout << ans << '\n';

}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}