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
#include <bits/stdc++.h>
#define un unsigned
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define per(i, a, b) for(ll i = a; i >= b; i--)
#define all(v) begin(v), end(v)
#define st first
#define nd second
using namespace std;
using ll = long long;
using bigi = __int128;
using pii = pair<ll, ll>;
const ll N = 1e6 + 5;
vector<vector<ll>> tab;
vector<vector<ll>> pre;
ll dpmal[N];
ll dpros[N];
void init(ll n, ll m){
    rep(i, 0, n){
        tab.push_back({});
        tab.back().resize(m + 5);
        pre.push_back({});
        pre.back().resize(m + 5);
    }
}
void poldpmal(vector<ll> mal, ll n, ll m){
    priority_queue<array<ll, 3>> pq;
    rep(i, 0, mal.size()){
        pq.push({tab[mal[i]][0], mal[i], 0});
    }
    rep(k, 1, mal.size() * m + 1){
        dpmal[k] = dpmal[k - 1] + pq.top()[0];
        auto [w, i, j] = pq.top();
        pq.pop();
        pq.push({tab[i][j + 1], i, j + 1});
    }
    rep(k, mal.size() * m + 1, n * m + 1){
        dpmal[k] = -1e18;
    }
}
void polros(vector<ll>& ros, int n, int m, int mod){
    if(ros.empty()) return;
    // cout << mod << endl;
    static set<pii> sumy;
    static vector<pii> pres;
    sumy.clear();
    pres.clear();
    for(auto i : ros){
        sumy.insert({pre[i][m], i});
        pres.push_back({pre[i][mod], i});
    }
    sort(all(pres));
    reverse(all(pres));
    dpros[mod] = pres.front().st;
    int wyb = pres.front().nd;
    sumy.erase({pre[wyb][m], wyb});
    rep(i, 1, pres.size()){
        // cout << "a " << sumy.size() << endl;
        // cout << i << ' ' << wyb << '\n';
        // cout << "sumy\n";
        // for(auto j : sumy) cout << j.st << ' ' << j.nd << '\n';
        // cout << "pres\n";
        // for(auto j : pres) cout << j.st << ' ' << j.nd << '\n';
        ll jakdodc = dpros[mod + (i - 1) * m] + prev(sumy.end()) -> st;
        ll jakdodnc = dpros[mod + (i - 1) * m] - pre[wyb][mod];
        sumy.insert({{pre[wyb][m], wyb}});
        int iledod = 1;
        bool bylo = 0;
        if(sumy.find(make_pair(pre[pres[i].nd][m], pres[i].nd)) == sumy.end()){
            iledod++;
            jakdodnc -= pre[pres[i].nd][m];
            // sumy.insert(make_pair(pre[pres[i].nd][m], pres[i].nd));
        }
        else{
            bylo = true;
            sumy.erase(make_pair(pre[pres[i].nd][m], pres[i].nd));
        }
        jakdodnc += pres[i].st;
        // cout << "jak " << jakdodnc << '\n';
        if(iledod > 0) jakdodnc += prev(sumy.end()) -> st;
        if(iledod > 1) jakdodnc += prev(prev(sumy.end())) -> st;
        // cout << "jakakak " << jakdodc << ' ' << jakdodnc << '\n';
        if(jakdodc > jakdodnc){
            sumy.erase({pre[wyb][m], wyb});
            if(bylo) sumy.insert({make_pair(pre[pres[i].nd][m], pres[i].nd)});
            sumy.erase(prev(sumy.end()));
            dpros[mod + i * m] = jakdodc;
        }
        else{
            wyb = pres[i].nd;
            if(iledod > 0) sumy.erase(prev(sumy.end()));
            if(iledod > 1) sumy.erase(prev(sumy.end()));
            dpros[mod + i * m] = jakdodnc;
        }
        // cout << "dp od " << i << ' ' << dpros[mod + i * m] << '\n';
        // cout << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    init(n, m);
    rep(i, 0, n){
        rep(j, 0, m){
            cin >> tab[i][j];
            pre[i][j + 1] = pre[i][j] + tab[i][j];
        }
    }
    vector<ll> ros, mal;
    rep(i, 0, n){
        if(tab[i][m - 1] > tab[i][0]){
            tab[i].push_back(1e18);
            ros.push_back(i);
        }
        else{
            tab[i].push_back(-1e18);
            mal.push_back(i);
        }
    }
    rep(i, 1, n * m + 1){
        dpros[i] = -1e18;
    }
    poldpmal(mal, n, m);
    rep(i, 1, m + 1){
        polros(ros, n, m, i);
    }
    ll maks = 0;
    rep(i, 0, k + 1){
        maks = max(maks, dpros[i] + dpmal[k - i]);
    }
    cout << maks << '\n';
}