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 int long long
using namespace std;

struct vec {
    vector<int> a;
    int sm;
    vec(vector<int> aa) : a(aa), sm(accumulate(aa.begin(), aa.end(), 0ll)) {}
    bool operator<(const vec& other) {
        return sm < other.sm;
    }
    bool operator>(const vec& other) {
        return sm > other.sm;
    }
};

bool incr(const vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++)
        if (a[i] > a[i - 1])
            return true;
    return false;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k; cin >> n >> m >> k;
    vector<vec> inc;
    vector<int> rest;
    for (int i = 0; i < n; i++) {
        vector<int> a(m);
        for (auto &j : a) cin >> j;
        if (incr(a)) {
            inc.push_back(move(a));
        }
        else {
            rest.insert(rest.end(), a.begin(), a.end());
        }
    }

    rest.push_back(LLONG_MAX);
    sort(rest.begin(), rest.end(), greater<>());
    rest[0] = 0;
    for (int i = 1; i < (int)rest.size(); i++) {
        rest[i] += rest[i - 1];
    }

    sort(inc.begin(), inc.end(), greater<>());
    vector<int> top(inc.size() + 1);
    for (int i = 1; i <= (int)inc.size(); i++) {
        top[i] = top[i - 1] + inc[i - 1].sm;
    }

    // dp[i][j] - dla sufiksu inc od i, maksymalna suma na prefiksie od j
    vector<vector<int>> dp(inc.size() + 1, vector<int>(m + 1, 0));
    for (int i = inc.size() - 1; i >= 0; i--) {
        vector<int> ps(m + 1, 0);
        for (int j = 1; j <= m; j++) {
            ps[j] = ps[j - 1] + inc[i].a[j - 1];
            dp[i][j] = max(dp[i + 1][j], ps[j]);
        }
    }

    // kp[i][j] - dla prefiksu inc do i, minimalna suma na sufiksie od j
    vector<vector<int>> kp(inc.size(), vector<int>(m + 1, LLONG_MAX));
    for (int i = 0; i < (int)inc.size(); i++) {
        vector<int> sf(m + 2, 0);
        for (int j = m; j >= 1; j--) {
            // cout << "i " << i << endl; 
            // cout << "j " << j << endl;
            // cout << "inc.size()" << inc.size() << endl;
            // cout << "inc[i].a.size()" << inc[i].a.size() << endl; 
            sf[j] = sf[j + 1] + inc[i].a[j - 1];
            kp[i][j] = min(i ? kp[i - 1][j] : LLONG_MAX, sf[j]);
        }
    }

    int ans = 0;
    for (int c = 0; c * m <= k && c <= (int)inc.size(); c++) {
        for (int r = 0; r < m && c * m + r <= k; r++) {
            if (k - c * m - r >= rest.size()) {
                continue;
            }
            if (c < (int)inc.size()) {
                int cur = max(
                    top[c + 1] - kp[c][r + 1],
                    top[c] + dp[c][r]
                );
                int res = rest[k - c * m - r];
                ans = max(ans, cur + res);
            }
            else {
                int cur = top[c] + dp[c][r];
                int res = rest[k - c * m - r];
                ans = max(ans, cur + res);
            }
        }
    }

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