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
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator << (auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) { (( cerr << x << ", " ), ...) <<
'\n'; }
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#define deb(...) 0
#endif
 
vector<ll> solveInc(vector<vector<ll>> v){
    int n = sz(v);
    if(n == 0)return {0};
    int m = sz(v[0]);
    vector<ll> ans(n * m + 1);
    rep(i, n){
        fwd(j, 1, m)v[i][j] += v[i][j-1];
    }
    vector<pair<ll, ll>> totalOrder;//stacks ordered by total sum
    rep(i, n)totalOrder.push_back({v[i][m-1], i});
    sort(all(totalOrder), greater<pair<ll, ll>>());
    deb(totalOrder);
    //k index of the last 
    rep(k, m){
        vector<pair<ll, ll>> prefOrder;
        rep(i, n)prefOrder.push_back({v[i][k], i});
        sort(all(prefOrder), greater<pair<ll, ll>>());
        deb(prefOrder);
        ans[k + 1] = prefOrder[0].st;
        deb(k+1, ans[k+1]);
        ll sum = 0;
        ll bestLoss = 1e18;
        int j = 0;
        vector<bool> used(n, false);
        rep(i, n-1){
            sum += totalOrder[i].st;
            used[totalOrder[i].nd] = true;
            bestLoss = min(bestLoss, totalOrder[i].st - v[totalOrder[i].nd][k]);
            while(used[prefOrder[j].nd])j++;
            int index = (i+1) * m + k + 1;
            ans[index] = max(sum + prefOrder[j].st, sum - bestLoss + v[totalOrder[i+1].nd][m-1]);
            deb(index, ans[index], i, j, sum, bestLoss);
        }
    }
    return ans;
}

vector<ll> solveDec(vector<vector<ll>> v){
    int n = sz(v);
    if(n == 0)return {0};
    int m = sz(v[0]);
    vector<ll> ans(n*m + 1);
    ans[0] = 0;
    vector<int> pos(n, 0);
    priority_queue<pair<ll, ll>> q;
    rep(i, n)q.push({v[i][0], i});
    fwd(j, 1, n * m + 1){
        auto [x, i] = q.top(); q.pop();
        pos[i]++;
        if(pos[i] < m)q.push({v[i][pos[i]], i});
        ans[j] = ans[j-1] + x;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<ll>> inc;
    vector<vector<ll>> dec;
    rep(i, n){
        vector<ll> v(m);
        rep(j, m)cin >> v[j];
        bool added = false;
        rep(j, m-1){
            if(v[j] < v[j+1]){
                inc.push_back(v);
                added = true;
                break;
            }else if(v[j] > v[j+1]){
                dec.push_back(v);
                added = true;
                break;
            }
        }
        if(!added)dec.push_back(v);
    }
    vector<ll> resDec = solveDec(dec);
    vector<ll> resInc = solveInc(inc);
    deb(resDec);
    deb(resInc);
    ll res = 0;
    for(int i = max(0, k - sz(resInc) + 1); i < sz(resDec) && i <= k; i++){
        res = max(res, resDec[i] + resInc[k-i]);
    }
    cout << res << "\n";
    return 0;
}