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

using namespace std;

// Struktura pomocnicza dla stosów Typu 1
struct StackInfo {
    long long val;
    int id;
    bool operator<(const StackInfo& other) const {
        return val > other.val; // sortowanie malejące po sumie
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long k;
    if (!(cin >> n >> m >> k)) return 0;

    vector<vector<long long>> prefix_stacks(n, vector<long long>(m + 1, 0));
    vector<bool> is_type1(n, false);
    vector<StackInfo> S;
    vector<long long> pool2;

    for (int i = 0; i < n; ++i) {
        vector<long long> a(m);
        for (int j = 0; j < m; ++j) {
            cin >> a[j];
            prefix_stacks[i][j + 1] = prefix_stacks[i][j] + a[j];
        }
        // Jeśli stos jest ściśle rosnący względem końców
        if (m > 1 && a[0] < a[m - 1]) {
            is_type1[i] = true;
            S.push_back({prefix_stacks[i][m], i});
        } else {
            // W przeciwnym razie to Typ 2 (nierosnący lub równe elementy)
            is_type1[i] = false;
            for (int j = 0; j < m; ++j) {
                pool2.push_back(a[j]);
            }
        }
    }

    sort(S.begin(), S.end());
    int N1 = S.size();
    vector<int> pos(n, -1);
    for (int i = 0; i < N1; ++i) {
        pos[S[i].id] = i;
    }

    vector<long long> S_prefix(N1 + 1, 0);
    for (int i = 0; i < N1; ++i) {
        S_prefix[i + 1] = S_prefix[i] + S[i].val;
    }

    sort(pool2.begin(), pool2.end(), greater<long long>());
    long long pool2_size = pool2.size();
    vector<long long> pool2_prefix(pool2_size + 1, 0);
    for (int i = 0; i < pool2_size; ++i) {
        pool2_prefix[i + 1] = pool2_prefix[i] + pool2[i];
    }

    long long ans = 0;

    // Przypadek 0: Nie bierzemy żadnego stosu Typu 1 w sposób częściowy (tylko całe i typ 2)
    long long p_max_0 = min((long long)N1, k / m);
    long long p_min_0 = 0;
    if (k > pool2_size) {
        p_min_0 = (k - pool2_size + m - 1) / m;
    }

    if (p_min_0 <= p_max_0) {
        auto eval0 = [&](long long p) -> long long {
            long long sum1 = S_prefix[p];
            long long x = k - p * m;
            return sum1 + pool2_prefix[x];
        };

        long long low = p_min_0, high = p_max_0;
        while (high - low > 2) {
            long long m1 = low + (high - low) / 3;
            long long m2 = high - (high - low) / 3;
            long long v1 = eval0(m1);
            long long v2 = eval0(m2);
            if (v1 < v2) low = m1;
            else if (v1 > v2) high = m2;
            else { low = m1; high = m2; }
        }

        for (long long p = low; p <= high; ++p) {
            ans = max(ans, eval0(p));
        }
    }

    // Przypadek 1: Dokładnie jeden stos Typu 1 jest wzięty częściowo
    for (int i = 0; i < n; ++i) {
        if (!is_type1[i]) continue;
        long long current_pos_i = pos[i];

        for (long long c = 1; c < m; ++c) {
            if (c > k) break;

            long long p_max = min((long long)(N1 - 1), (k - c) / m);
            long long p_min = 0;
            if (k - c > pool2_size) {
                p_min = (k - c - pool2_size + m - 1) / m;
            }

            if (p_min > p_max) continue;

            auto eval1 = [&](long long p) -> long long {
                long long sum1 = 0;
                if (p > 0) {
                    if (current_pos_i >= p) {
                        sum1 = S_prefix[p];
                    } else {
                        sum1 = S_prefix[p + 1] - S[current_pos_i].val;
                    }
                }
                long long x = k - c - p * m;
                return sum1 + pool2_prefix[x];
            };

            // Ternary Search w celu znalezienia optymalnej ilości p pełnych stosów
            long long low = p_min, high = p_max;
            while (high - low > 2) {
                long long m1 = low + (high - low) / 3;
                long long m2 = high - (high - low) / 3;
                long long v1 = eval1(m1);
                long long v2 = eval1(m2);
                if (v1 < v2) low = m1;
                else if (v1 > v2) high = m2;
                else { low = m1; high = m2; }
            }

            long long best_val = -1;
            for (long long p = low; p <= high; ++p) {
                best_val = max(best_val, eval1(p));
            }
            ans = max(ans, best_val + prefix_stacks[i][c]);
        }
    }

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