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
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

bool cmp(vector<int>& a, vector<int>& b) {
    return a.back() > b.back();
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> v(n, vector<int>(m)), v2;
    rep(i, 0, n) rep(j, 0, m) cin >> v[i][j];
    priority_queue<int> pq;
    rep(i, 0, n) {
        bool asc = 0;
        rep(j, 1, m) if(v[i][j] > v[i][j - 1]) { asc = 1; break; }
        if(asc) v2.pb(v[i]);
        else repIn(j, v[i]) pq.push(j);
    }
    int n2 = (int)v2.size();
    rep(i, 0, n2) rep(j, 0, m - 1) v2[i][j + 1] += v2[i][j];
    rg::sort(v2, cmp);
    vector<int> prefB(n2);
    int prf = 0;
    rep(i, 0, n2) prf += v2[i].back(), prefB[i] = prf;
    vector<vector<int>> dp(n2, vector<int>(m));
    repD(i, n2 - 1, -1) rep(j, 0, m) dp[i][j] = max((i == n2 - 1 ? -1 : dp[i + 1][j]), v2[i][j]);
    rep(i, 0, n2) rep(j, 0, m) dp[i][j] = max(dp[i][j] + (i ? prefB[i - 1] : 0), (i ? dp[i - 1][j] + v2[i].back() : -2137));
    int ans = 0;
    int curAns = 0;
    int inCur = 0;
    repD(i, n2 - 1, -1) repD(j, m - 1, -1) if(i * m + j + 1 <= k) {
        while(inCur < k - (i * m + j + 1) && pq.size()) inCur++, curAns += pq.top(), pq.pop();
        if(inCur < k - (i * m + j + 1)) break;
        ans = max(ans, curAns + dp[i][j]);
    }
    while(inCur < k && pq.size()) inCur++, curAns += pq.top(), pq.pop();
    if(inCur == k) ans = max(ans, curAns);
    cout << ans << '\n';
}