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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Stack {
    vector<long long> values;
    long long sum;
    vector<long long> prefixSums;
};

void resolveSingles(long long n, long long k) {
    vector<long long> stacks(n);
    for (long long i = 0; i < n; i++) {
        cin >> stacks[i];
    }
    sort(stacks.begin(), stacks.end(), greater<long long>());
    long long sum = 0;
    for (long long i = 0; i < k; i++) {
        sum += stacks[i];
    }
    cout << sum << endl;
}

bool isIncreasing(const vector<long long> &stack) {
    for (size_t i = 1; i < stack.size(); i++) {
        if (stack[i - 1] > stack[i]) {
            return false;
        }
    }
    return true;
}

long long getResult(const vector<long long> &increasingPrefixes, const vector<Stack> &increasing,
    long long incompleteIndex, long long fullStacks, long long m) {
    long long result = increasingPrefixes[incompleteIndex];

    for (long long i = 0; i < fullStacks; i++) {
        long long j = i >= incompleteIndex ? i + 1 : i;
        result += increasing[j].sum;
    }
    return result;
}

long long checkMax(long long currentMax, long long result,
    const vector<long long> &decreasingPrefixes, long long fullStacks, long long remainder, long long k, long long m, long long n) {
    long long decreasingCount = k - (fullStacks * m + remainder);
    if (decreasingCount < 0 || (size_t)decreasingCount >= decreasingPrefixes.size()) {
        return currentMax;
    }
    return max(currentMax, result + decreasingPrefixes[decreasingCount]);
}

long long resolveRemainder(const vector<Stack> &increasing, const vector<long long> &decreasingPrefixes,
    long long remainder, long long k, long long m, long long n) {
    if (increasing.empty()) {
        return decreasingPrefixes[k];
    }

    if (remainder == 0) {
        long long result = 0;
        long long currentMax = 0;
        currentMax = checkMax(currentMax, result, decreasingPrefixes, 0, 0, k, m, n);
        for (long long fullStacks = 1; fullStacks * m <= k; fullStacks++) {
            if (fullStacks > increasing.size()) {
                break;
            }
            result += increasing[fullStacks - 1].sum;
            currentMax = checkMax(currentMax, result, decreasingPrefixes, fullStacks, remainder, k, m, n);
        }
        return currentMax;
    }

    set<pair<long long, long long>> prefixesSet;
    for (long long i = 0; i < increasing.size(); i++) {
        prefixesSet.insert({increasing[i].prefixSums[remainder], i});
    }

    long long currentMax = 0;
    long long fullStacksSum = 0;
    long long incompleteIndex = prev(prefixesSet.end())->second;
    long long result = increasing[incompleteIndex].prefixSums[remainder];
    currentMax = checkMax(currentMax, result, decreasingPrefixes, 0, remainder, k, m, n);

    for (long long fullStacks = 1; fullStacks * m + remainder <= k; fullStacks++) {
        if (fullStacks >= increasing.size()) {
            break;
        }
        fullStacksSum += increasing[fullStacks - 1].sum;
        prefixesSet.erase({increasing[fullStacks - 1].prefixSums[remainder], fullStacks - 1});
        if (incompleteIndex >= fullStacks) {
            result = increasing[incompleteIndex].prefixSums[remainder] + fullStacksSum;
        } else {
            long long result1 = increasing[incompleteIndex].prefixSums[remainder] + fullStacksSum
                - increasing[incompleteIndex].sum + increasing[fullStacks].sum;
            long long result2 = 0;
            if (!prefixesSet.empty()) {
                long long newIncompleteIndex = prev(prefixesSet.end())->second;
                result2 = increasing[newIncompleteIndex].prefixSums[remainder] + fullStacksSum;
                if (result2 > result1) {
                    incompleteIndex = newIncompleteIndex;
                }
            }
            result = max(result1, result2);
        }
        currentMax = checkMax(currentMax, result, decreasingPrefixes, fullStacks, remainder, k, m, n);
    }
    return currentMax;
}

void resolveMultiples(long long n, long long m, long long k) {
    vector<Stack> increasing;
    vector<long long> decreasing;
    for (long long i = 0; i < n; i++) {
        vector<long long> stack(m);
        long long sum = 0;
        for (long long j = 0; j < m; j++) {
            cin >> stack[j];
            sum += stack[j];
        }
        if (isIncreasing(stack)) {
            vector<long long> ps(m + 1);
            for (long long j = 0; j < m; j++) {
                ps[j + 1] = ps[j] + stack[j];
            }
            increasing.push_back({stack, sum, ps});
        } else {
            decreasing.insert(decreasing.end(), stack.begin(), stack.end());
        }
    }

    sort(increasing.begin(), increasing.end(), [](const Stack &a, const Stack &b) {
        return a.sum > b.sum;
        });

    sort(decreasing.begin(), decreasing.end(), greater<long long>());
    vector<long long> decreasingPrefixes(decreasing.size() + 1);
    for (size_t i = 0; i < decreasing.size(); i++) {
        decreasingPrefixes[i + 1] = decreasingPrefixes[i] + decreasing[i];
    }

    long long max = 0;
    for (long long i = 0; i <= m; i++) {
        long long result = resolveRemainder(increasing, decreasingPrefixes, i, k, m, n);
        if (result > max) {
            max = result;
        }
    }
    cout << max << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, k;
    cin >> n >> m >> k;

    if (m == 1) {
        resolveSingles(n, k);
    } else {
        resolveMultiples(n, m, k);
    }

}