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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef double db;
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#define rep(i, l, r) for(int i=l; i<(r); i++)

ll nxt(){
    ll x;
    cin >> x;
    return x;
}
const int debug = 0;

const ll inf = 1e18;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vll> rosnace;
    vector<vll> malejace;
    for(int i=0; i<n; i++) {
        vll nowy(m);
        for(auto &e : nowy) cin >> e;
        reverse(all(nowy));
        bool malejacy = 1;
        for(int i=1; i<m; i++) {
            if(nowy[i] > nowy[i-1]) malejacy = 0;
        }
        if(malejacy) malejace.push_back(nowy);
        else rosnace.push_back(nowy);
    }
    vll zros(m*rosnace.size()+1);
    vll zmal(m*malejace.size()+1);
    priority_queue<pair<ll, pii>> pq;
    for(int i=0; i<rosnace.size(); i++) {
        pq.push({rosnace[i].back(), (pii){i, m-1}});
    }
    zros[0] = 0;
    int ktory = 1;
    while(!pq.empty()) {
        auto pa = pq.top();
        pq.pop();
        zros[ktory] = zros[ktory-1] + pa.first;
        ktory++;
        pa.second.second--;
        if(pa.second.second>=0) pq.push({rosnace[pa.second.first][pa.second.second], pa.second});
    }
    zmal[0] = 0;
    int N = malejace.size();
    vector<pair<ll, int>> sumy;
    vector<ll> prefy(N, 0);
    for(int i=0; i<N; i++) {
        ll s = 0;
        for(auto e : malejace[i]) s += e;
        sumy.push_back({s, i});
    }
    sort(all(sumy));
    reverse(all(sumy));
    vector<ll> sumy_prefixowe_calych(N+1, 0);
    for(int i=1; i<=N; i++) {
        sumy_prefixowe_calych[i] = sumy_prefixowe_calych[i-1] + sumy[i-1].first;
    }

    for(int reszta = 1; reszta <= m; reszta++) {
        for(int i = 0; i < N; i++) prefy[i] += malejace[sumy[i].second][m-reszta];

        ll najmniejszy_spadek = inf;
        ll suma_wszystkich = 0;
        for(int i=0; i<N; i++) {
            najmniejszy_spadek = min(najmniejszy_spadek, sumy[i].first - prefy[i]);
            zmal[i*m + reszta] = max(zmal[i*m + reszta], sumy_prefixowe_calych[i+1] - najmniejszy_spadek);
        }
        ll najwieksza_czastka = 0;
        for(int i=N-1; i>=0; --i) {
            najwieksza_czastka = max(najwieksza_czastka, prefy[i]);
            zmal[i*m + reszta] = max(zmal[i*m + reszta], sumy_prefixowe_calych[i] + najwieksza_czastka);
        }
    }
    ll ans = 0;
    if(debug) {
        cout << "z malejacych:\n";
        for(int i=0; i<zmal.size(); i++) {
            cout << "i = "<<i<<";  zmal[i] = "<<zmal[i]<<"\n";
        }
        cout << "z rosnacych:\n";
        for(int i=0; i<zros.size(); i++) {
            cout << "i = "<<i<<";  zros[i] = "<<zros[i]<<"\n";
        }
    }
    for(int i=0; i<=k; i++) {
        if((i < zmal.size()) && (k-i < zros.size())){
            if(zmal[i] + zros[k-i] == 12) cout << i << "\n";
            ans = max(ans, zmal[i]+zros[k-i]);
        }

    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}