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

#define nd second
#define st first
#define int long long

struct Cmp {
    bool operator()(const pair<int, pair<int,int>>& a, const pair<int,pair<int,int> >& b) const {
        return a.st > b.st;
    }
};

bool cmp(vector<int> &a, vector<int> &b) {
    if(a.back() < b.back())
        return true;
    return false;
}

int get_from_bests(vector<int> &vis, vector<priority_queue<pair<int,int> > > &q, int k) {
    while(q[k].size() && vis[q[k].top().nd]) {
        q[k].pop();
    }
    return q[k].top().st;
}

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

    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<int> > v(n, vector<int> (m));
    vector<int> dec;
    vector<int> sums(n);
    int tak = 0;
    vector<priority_queue<pair<int,int> > > bests(m+1);
    for(int i=0; i<n; i++) {
        int sum = 0;
        bool d = true;
        for(int j=0; j<m; j++) {
            cin>>v[i][j];
            sum += v[i][j];
            if(j>0 && v[i][j-1]<v[i][j])
                d = false;
        }
        if(d) {
            for(int j=0; j<m; j++)
                dec.push_back(v[i][j]);
        }
        else {
            v[i].push_back(sum);
            tak += m;
            int sum2 = 0;
            for(int j=0; j<m; j++) {
                sum2+=v[i][j];
                bests[j+1].push({sum2, i});
            }
        }
        sums[i] = sum;
    }

    sort(dec.begin(), dec.end());
    int res = 0;
    int d_ind = dec.size()-1;
    while(d_ind>=0 && k>0) {
        k--;
        res+= dec[d_ind];
        d_ind--;
    }
    d_ind ++;
    vector<int> vis(n+1, 0);
    while(k>=m) {
        auto t = bests[m].top();
        bests[m].pop();
        res+=t.st;
        vis[t.nd] = 1;
        k-=m;
        tak -= m;
    }

    tak -= k;
    
    
    int act_res = res;
    if(k>0) 
        act_res += get_from_bests(vis, bests, k);
    while(d_ind<dec.size() && tak>0) {
  //  cout<<"A"<<endl;
       // cout<<d_ind<<" "<<tak<<endl;
        res -= dec[d_ind];
        d_ind ++;
        k++;
       // cout<<res<<" "<<act_res<<" "<<k<<" "<<get_from_bests(vis, bests, k)<<endl;
        
        if(k == m) {
            auto t = bests[m].top();
            bests[m].pop();
            res+=t.st;
            vis[t.nd] = 1;
            k-=m;
            act_res = max(res, act_res);
        }
        else {
            act_res = max(act_res, res+ get_from_bests(vis, bests, k));
        }
        tak--;
    }

    cout<<act_res;

}