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
#include <bits/stdc++.h>
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define V vector
using namespace std;
typedef long long ll;
int mod = 119<<23|1;
ll infll = 2e18;
int add(int a, int b) { return a+b >= mod ? a+b-mod : a+b; }
int sub(int a, int b) { return add(mod-b, a); }
int mul(int a, int b) { return int(a*ll(b)%mod); }
int fpow(int a, int b = mod-2) {
    int res = 1;
    while(b) {
        if (b & 1) res = mul(res, a);
        b >>= 1, a = mul(a, a);
    }
    return res;
}
int divd(int a, int b) {
    assert(b != 0);
    return mul(a, fpow(b));
}

template<typename... Args>
void read(Args&... args) {
    auto read_one = [&](auto &a) {
        a = 0; int c = getchar_unlocked();
        while (c < '0' || '9' < c) c = getchar_unlocked();
        while ('0' <= c && c <= '9') a = a*10+c-'0', c = getchar_unlocked();
    };
    return (read_one(args), ...);
}

void answer() {
    int n, m, k; read(n, m, k);
    V<V<ll>> up, down;
    V<ll> in; in.resize(m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) read(in[j]);
        int u = 0;
        for (int j = 1; j < m; ++j)
            if (in[j-1] < in[j]) u = 1;
        
        if (u) up.emplace_back(in);
        else down.emplace_back(in);
    }
    
    // rosnace
    int N = ssize(up);
    V<int> up_order(N); iota(all(up_order), 0);
    for (int i = 0; i < N; ++i)
        accumulate(all(up[i]), 0ll, [&](auto acc, auto &x) { return x += acc; });
    sort(rall(up_order), [&](int a, int b) { return up[a][m-1] < up[b][m-1]; });

    V<V<ll>> up2(N);
    for (int i = 0; i < N; ++i)
        up2[i] = move(up[up_order[i]]);
    up = move(up2); // teraz upy są posortowane

    V<ll> res_up(n*m+1, 0), suf_max(N+1, 0);
    for (int r = 0; r < m; ++r) {
        fill(all(suf_max), 0);
        for (int i = N-1; ~i; --i)
            suf_max[i] = max(suf_max[i+1], r ? up[i][r-1] : 0);

        ll min_diff = infll, sum = 0;
        for (int i = 0; i < N; ++i) {
            res_up[i*m+r] = max(sum+suf_max[i], sum-min_diff+up[i][m-1]);
            sum += up[i][m-1];
            min_diff = min(min_diff, up[i][m-1]-(r ? up[i][r-1] : 0));
        }
        if (!r) res_up[N*m] = sum;
    }

    // malejace
    N = ssize(down);
    V<ll> res_down(1, 0); res_down.reserve(n*m+1);
    priority_queue<pair<ll, ll>> pq;
    for (int i = 0; i < N; ++i) {
        reverse(all(down[i]));
        pq.emplace(down[i].back(), i), down[i].pop_back();
    }
    
    while (ssize(pq)) {
        auto [val, i] = pq.top(); pq.pop();
        res_down.emplace_back(res_down.back()+val);
        if (ssize(down[i]))
            pq.emplace(down[i].back(), i), down[i].pop_back();
    }
    res_down.resize(k+1);

    ll result = 0;
    for (int i = 0; i <= k; ++i) result = max(result, res_up[i]+res_down[k-i]);
    printf("%lld\n", result);
}
int main() {
    int T = 1; //scanf("%d", &T);
    for (++T; --T; ) answer();
    return 0;
}