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

using ll = long long;

const ll INF = 1e18;

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<ll> answersDecresing(k + 1, 0);
    std::vector<ll> answersIncreasing(k + 1, 0);

    std::vector<std::pair<ll, std::vector<ll>>> pI;
    std::vector<ll> pD;

    for (int i = 0; i < n; i++) {
        std::vector<ll> p(m);
        bool isIncreasing = false;
        ll sum = 0;

        for (int j = 0; j < m; j++) {
            std::cin >> p[j];
            sum += p[j];
            if (j > 0 && p[j - 1] < p[j]) {
                isIncreasing = true;
            }
        }

        if (isIncreasing) {
            pI.push_back({sum, std::move(p)});
        } else {
            pD.insert(pD.end(), p.begin(), p.end());
        }
    }

    std::ranges::sort(pD, std::greater<ll>());
    // answersDecreasing calculations
    for (int i = 0; i < k; i++) {
        ll delta = 0;
        if (i < pD.size()) {
            delta = pD[i];
        }

        answersDecresing[i + 1] = answersDecresing[i] + delta;
    }

    // answersIncreaing calculations
    std::ranges::sort(pI, [](const auto &a, const auto &b) -> bool {
        return a.first > b.first;
    });

    int pin = pI.size();

    // sum of n first and deduct l from them
    std::vector<std::pair<ll, std::vector<ll>>> t1(pin + 1, {0, std::vector<ll>(m + 1, INF)});
    std::vector<std::vector<ll>> t2(pin + 1, std::vector<ll>(m + 1, 0));

    for (int i = 0; i < pin; i++) {
        t1[i + 1].first = t1[i].first + pI[i].first;
        t1[i + 1].second[m] = 0;

        ll tempsum = 0;
        for (int j = m - 1; j >= 0; j--) {
            tempsum += pI[i].second[j];
            t1[i + 1].second[j] = std::min(
                t1[i].second[j],
                tempsum
            );
        }
    };

    // merge same sums
    for (int i = pin - 1; i > 0; i--) {
        if (pI[i].first == pI[i - 1].first) {
            for (int j = 0; j < m; j++) {
                t1[i].second[j] = std::min(t1[i].second[j], t1[i + 1].second[j]);
            }
        }
    }

    // biggest pref from n last
    for (int i = 0; i < pin; i++) {
        ll tempsum = 0;
        for (int j = 0; j < m; j++) {
            tempsum += pI[pin - 1 - i].second[j];
            t2[i + 1][j + 1] = std::max(tempsum, t2[i][j + 1]);
        }
    }

    for (int i = 1; i <= k; i++) {
        if (i > pin * m) continue;

        int full_stacks = i / m;
        int rest = i % m;

        answersIncreasing[i] = t1[full_stacks].first + t2[pin - full_stacks][rest];

        if (rest != 0) {
            answersIncreasing[i] = std::max(
                answersIncreasing[i],
                t1[full_stacks + 1].first - t1[full_stacks + 1].second[rest]
            );
        }
    }

    // Conculsion
    ll answer = 0;
    for (int i = 0; i <= k; i++) {
        answer = std::max(
            answer,
            answersDecresing[i] + answersIncreasing[k - i]
        );
    }

    std::cout << answer << "\n";
}