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
118
#include <algorithm>
#include <iostream>
#include <vector>
#include <ranges>

using namespace std;

typedef unsigned long long ull;

class PrefixSumStack {
    std::vector<ull> prefix_sums;
    size_t head_index = 0;

public:
    void push_back(const ull value) {
        if (prefix_sums.empty()) {
            prefix_sums.push_back(value);
        } else {
            prefix_sums.push_back(prefix_sums.back() + value);
        }
    }

    ull get_sum_of_first(ull k) const {
        if (k == 0) return 0;
        const ull sum_at_end = prefix_sums[head_index + k - 1];
        const ull sum_before_start = (head_index == 0) ? 0 : prefix_sums[head_index - 1];
        return sum_at_end - sum_before_start;
    }

    void pop_front(const ull k) {
        head_index += k;
    }

    ull size() const {
        return prefix_sums.size() - head_index;
    }

    void print() const {
        vector<ull> v = prefix_sums;
        for (const auto x: v) {
            cout << x << " ";
        }
        cout << endl;
    }
};

int main() {
    ios_base::sync_with_stdio(false);

    ull n, m, k;
    cin >> n >> m >> k;

    vector<PrefixSumStack> stacks;
    vector<ull> to_sort;
    for (ull i = 0; i < n; i++) {
        bool asc = true;
        ull prev = 0;
        ull curr;
        vector<ull> raw_stack;
        for (ull j = 0; j < m; j++) {
            cin >> curr;
            raw_stack.push_back(curr);
            if (prev > curr) {
                asc = false;
            }
            prev = curr;
        }
        if (asc) {
            auto stack = PrefixSumStack();
            for (const auto x: raw_stack) {
                stack.push_back(x);
            }
            stacks.push_back(stack);
        } else {
            for (const auto x: raw_stack) {
                to_sort.push_back(x);
            }
        }
    }

    ranges::sort(to_sort, [](const ull a, const ull b) {
        return a > b;
    });

    if (!to_sort.empty()) {
        for (ull i = 0; i < to_sort.size(); i += m) {
            std::span chunk(to_sort.data() + i, m);
            auto stack = PrefixSumStack();
            for (const auto x: chunk) {
                stack.push_back(x);
            }
            stacks.push_back(stack);
        }
    }

    std::ranges::sort(stacks, [m](const PrefixSumStack &a, const PrefixSumStack &b) {
        return a.get_sum_of_first(m) > b.get_sum_of_first(m);
    });

    ull sum = 0;
    ull i = 0;
    while (k > m) {
        sum += stacks[i].get_sum_of_first(m);
        i++;
        k -= m;
    }

    ull max = 0;
    for (int j = i; j < stacks.size(); j++) {
        if (stacks[j].get_sum_of_first(k) > max) {
            max = stacks[j].get_sum_of_first(k);
        }
    }

    cout << sum + max << endl;

    return 0;
}