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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define BOOST ios_base::sync_with_stdio(0), cin.tie(0)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
const ll INF = 1e18;
void test_case() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> v;
    vector<ll> other;
    for (int i = 0; i < n; i++) {
        bool inc = false;
        vector<ll> vec(m);
        for (int j = 0; j < m; j++) {
            cin >> vec[j];
            inc |= j > 0 && vec[j - 1] < vec[j];
        }
        if (!inc) {
            for (auto x : vec)
                other.push_back(x);
        } else {
            v.push_back(vec);
        }
    }

    sort(other.rbegin(), other.rend());
    int l = v.size();
    if (l == 0) {
        ll sum = 0;
        for (int i = 0; i < k; i++) {
            sum += other[i];
        }
        cout << sum << "\n";
        return;
    }

    vector<vector<pair<ll, int>>> sums(m + 1, vector<pair<ll, int>>(l));
    for (int i = 0; i < l; i++)
        sums[0][i] = {0, i};

    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < l; j++) {
            sums[i][j].fi = sums[i - 1][j].fi + v[j][i - 1];
            sums[i][j].se = j;
        }
    }

    sort(sums[m].begin(), sums[m].end(), [&](auto &p1, auto &p2) {
        if (p1.fi == p2.fi) {
            return p1.se < p2.se;
        } else
            return p1.fi > p2.fi;
    });

    vector<vector<ll>> sums2(m + 1, vector<ll>(l, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < l; j++) {
            sums2[i][j] = sums[i][(i < m ? sums[m][j].se : j)].fi;
        }
    }

    vector<ll> best(m * l + 1, 0);
    for (int i = 0; i < l; i++)
        best[m * l] += sums2[m][i];

    for (int i = 0; i <= m - 1; i++) {
        multiset<ll> mst(sums2[i].begin(), sums2[i].end());
        best[i] = *prev(mst.end());
        int cur_min = -1;
        ll cur_delta = INF, cur_pref = 0;
        for (int j = 0; j < l - 1; j++) {
            if (cur_delta > sums2[m][j] - sums2[i][j]) {
                cur_delta = sums2[m][j] - sums2[i][j];
                cur_min = j;
            }
            cur_pref += sums2[m][j];
            mst.extract(sums2[i][j]);
            ll best_ans = cur_pref + *prev(mst.end());
            best_ans = max(best_ans, cur_pref - sums2[m][cur_min] + sums2[i][cur_min] + sums2[m][j + 1]);
            best[i + (j + 1) * m] = best_ans;
        }
    }

    ll ans = (m * l >= k ? best[k] : 0);
    ll cur_pref = 0;
    for (int j = 0; j < min(k, (int)other.size()); j++) {
        cur_pref += other[j];
        if (k - j - 1 <= m * l)
            ans = max(ans, cur_pref + best[k - j - 1]);
    }
    cout << ans << "\n";
}
int32_t main() {
    BOOST;
    int q = 1;
    // cin >> q;

    while (q--) {
        test_case();
    }
}