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

void solve(){
    ll n, m, k; cin>>n>>m>>k;

    vector<vector<ll>> blues, reds;

    for(ll i=0; i<n; i++){
        bool red = 1;
        vector<ll> v(m, 0);
        for(ll j=0; j<m; j++){
            cin>>v[j];
            if(j != 0 && v[j] > v[j-1]) red = 0;
        }

        if(red) reds.push_back(v);
        else blues.push_back(v);
    }

    //-------------------------- reds
    vector<ll> takeReds(k+1, 0);
    vector<ll> pointersReds(reds.size(), 0);

    priority_queue<pair<ll, ll>> pq;
    for(ll i=0; i<(ll)reds.size(); i++) pq.push({reds[i][0], i});

    for(ll i=1; i<=k; i++){
        if(pq.empty()) break;
        takeReds[i] = takeReds[i-1] + pq.top().first;
        ll id = pq.top().second;
        pq.pop();
        pointersReds[id]++;
        if(pointersReds[id] < m) pq.push({reds[id][pointersReds[id]], id});
    }

    //-------------------------- blues
    vector<ll> takeBlues(k+1, 0);

    if(blues.size() != 0){
        for(ll i=0; i<(ll)blues.size(); i++){
            ll sum = accumulate(blues[i].begin(), blues[i].end(), 0LL);
            blues[i].insert(blues[i].begin(), sum);
        }

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

        ll bs = blues.size();

        if((ll)takeBlues.size() < bs * m + 1){
            takeBlues.resize(bs * m + 1, 0);
        }

        for(ll i=m; i <= bs * m; i+=m){
            takeBlues[i] = takeBlues[i-m] + blues[(i/m)-1][0];
        }

        // change blues to prefBlues
        for(ll i=0; i<(ll)blues.size(); i++){
            for(ll j=2; j<(ll)blues[i].size(); j++) blues[i][j] = blues[i][j-1] + blues[i][j];
        }


        vector<vector<ll>> suffHelp(bs + 1, vector<ll>(m, 0));
        vector<vector<ll>> prefHelp(bs + 1, vector<ll>(m, -(1LL<<60)));

        for(ll i=bs-1; i>=0; i--){
            for(ll j=1; j<m; j++){
                suffHelp[i][j] = max(suffHelp[i+1][j], blues[i][j]);
            }
        }

        for(ll i=0; i<bs; i++){
            for(ll j=1; j<m; j++){
                prefHelp[i+1][j] = max(prefHelp[i][j], blues[i][j] - blues[i][0]);
            }
        }

        // calc
        for(ll i=1; i<=k; i++){
            if(i > bs * m) break;
            if(i % m == 0) continue;
            ll part = i/m, res = i % m;
            ll best = 0;

            if(part < bs){
                best = max(best, takeBlues[part*m] + suffHelp[part][res]);
            }

            if(part > 0 && part < bs){
                best = max(best, takeBlues[(part+1)*m] + prefHelp[part][res]);
            }

            takeBlues[i] = best;
        }
    }

    //-------------------------- ans

    ll ans = 0;
    for(ll i=0; i<=k; i++) ans = max(ans, takeReds[i] + takeBlues[k-i]);
    cout<<ans<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
 
    int sets=1; 
    //cin>>sets;
    while(sets--){
        solve();
    }
    return 0;
}