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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int m;
int k;
vector<vector<long long>> pancakes;
vector<long long> all_pancakes_from_desc_stacks_sums;
vector<vector<long long>> stacks_sums;
vector<int> asc_stacks_ids_sorted_from_the_biggest;
vector<vector<int>> best_x_items_from_asc_stacks_from_the_left;
vector<vector<int>> best_x_items_from_asc_stacks_from_the_right;

int main() {
  // read data
  scanf("%d %d %d", &n, &m, &k);
  for (int stack_id = 0; stack_id < n; stack_id++) {
    vector<long long> temp_pancakes_stack;
    for (int pancake_id = 0; pancake_id < m; pancake_id++) {
      long long temp_pancake;
      scanf("%lld", &temp_pancake);
      temp_pancakes_stack.push_back(temp_pancake);
    }
    pancakes.push_back(temp_pancakes_stack);
  }

  // prepare sums for each stack - item under index X contains sum of all pancakes sizes from the beginning (including X)
  // (probably we don't need to sum descending stacks, but it doesn't hurt)
  for (int stack_id = 0; stack_id < n; stack_id++) {
    long long temp_sum = 0LL;
    vector<long long> temp_stack_sums;
    for (int pancake_id = 0; pancake_id < m; pancake_id++) {
      temp_sum += pancakes[stack_id][pancake_id];
      temp_stack_sums.push_back(temp_sum);
    }
    stacks_sums.push_back(temp_stack_sums);
  }

  // iterate to identify (and prepare for precomputation) ascending and descending stacks
  for (int stack_id = 0; stack_id < n; stack_id++) {
    if (pancakes[stack_id][0] >= pancakes[stack_id][m - 1]) { // if first panckae is bigger than the last on (or equal), it's descending stack
      // if it's descending stack, then we can always choose greedily the biggest pancake from any desc stack (and repeate X times);
      // so put them in one place (to later sort it and sum it - from the biggest to the smallest!)
      for (int pancake_id = 0; pancake_id < m; pancake_id++) {
        all_pancakes_from_desc_stacks_sums.push_back(pancakes[stack_id][pancake_id]);
      }
    } else { // otherwise it's ascending stack
      // then add ID of this stack to the list of ascending stacks
      asc_stacks_ids_sorted_from_the_biggest.push_back(stack_id);
    }
  }

  // prepare big pile of pancakes collected from descending stacks
  // first - sort it - from the biggest to the smallest
  sort(all_pancakes_from_desc_stacks_sums.begin(), all_pancakes_from_desc_stacks_sums.end(), [](long long a, long long b) {
    return a > b;
  });

  // printf("DESC PILE DUMP - AFTER SORT:\n");
  // for (int i = 0; i < all_pancakes_from_desc_stacks_sums.size(); i++) {
  //   printf("%lld ", all_pancakes_from_desc_stacks_sums[i]);
  // }
  // printf("\n");

  // then - sum it
  long long temp_sum_for_desc = 0LL;
  for (int pancake_id = 0; pancake_id < all_pancakes_from_desc_stacks_sums.size(); pancake_id++) {
    temp_sum_for_desc += all_pancakes_from_desc_stacks_sums[pancake_id];
    all_pancakes_from_desc_stacks_sums[pancake_id] = temp_sum_for_desc;
  }

  // printf("DESC PILE DUMP - AFTER SUM:\n");
  // for (int i = 0; i < all_pancakes_from_desc_stacks_sums.size(); i++) {
  //   printf("%lld ", all_pancakes_from_desc_stacks_sums[i]);
  // }
  // printf("\n");

  // special case - if we don't have any ascending stacks, then answer is super simple - k pancakes from the big pile
  if (asc_stacks_ids_sorted_from_the_biggest.empty()) {
    printf("%lld\n", all_pancakes_from_desc_stacks_sums[k - 1]); // index shift - starting from 0
    return 0;
  }

  // now sort ascending stacks (their IDs) - from the biggest (in terms of sum of items) to the smallest
  sort(asc_stacks_ids_sorted_from_the_biggest.begin(), asc_stacks_ids_sorted_from_the_biggest.end(), [](int a, int b) {
    return stacks_sums[a][m - 1] > stacks_sums[b][m - 1]; // (m - 1) is the last item from sums, equal to the sum of all pancakes from the stack
  });

  // printf("DESC STACKS IDS DUMP - AFTER SORT:\n");
  // for (int i = 0; i < asc_stacks_ids_sorted_from_the_biggest.size(); i++) {
  //   printf("%d: %lld\n", asc_stacks_ids_sorted_from_the_biggest[i], stacks_sums[asc_stacks_ids_sorted_from_the_biggest[i]][m - 1]);
  // }
  // printf("\n");

  // preparation of 2 additional arrays to quickly answer which asecnding stack to choose, when I need to choose X pancakes from it
  // init vectors
  for (int indirect_stack_id = 0; indirect_stack_id < asc_stacks_ids_sorted_from_the_biggest.size(); indirect_stack_id++) {
    vector<int> temp_vector;
    temp_vector.push_back(-1); // add item with ID 0, which will not be used
    best_x_items_from_asc_stacks_from_the_left.push_back(temp_vector);
    best_x_items_from_asc_stacks_from_the_right.push_back(temp_vector);
  }
  
  // array to choose from the left from ID of sorted ascending stacks
  // iterate over the number of pancakes we will need to choose (without M itself - it would mean the whole stack)
  for (int number_of_pancakes = 1; number_of_pancakes < m; number_of_pancakes++) {
    int the_best_stack_id = asc_stacks_ids_sorted_from_the_biggest[0];
    long long the_best_value = stacks_sums[the_best_stack_id][number_of_pancakes - 1] - stacks_sums[the_best_stack_id][m - 1];
    for (int indirect_stack_id = 0; indirect_stack_id < asc_stacks_ids_sorted_from_the_biggest.size(); indirect_stack_id++) {
      int temp_stack_id = asc_stacks_ids_sorted_from_the_biggest[indirect_stack_id];
      // indices shift again, in stacks sum starting from 0, so need to decrease 1...

      // vvvvv BUGGY vvvvv, I need to optimise diff between sum to that point MINUS SUM OF THE STACK! (smallest loss)
      // if (stacks_sums[temp_stack_id][number_of_pancakes - 1] > stacks_sums[the_best_stack_id][number_of_pancakes - 1]) {
      //   the_best_stack_id = temp_stack_id;
      // }
      // ^^^^^ BUGGY ^^^^^


      long long temp_value = stacks_sums[temp_stack_id][number_of_pancakes - 1] - stacks_sums[temp_stack_id][m - 1];
      if (temp_value > the_best_value) {
        the_best_stack_id = temp_stack_id;
        the_best_value = temp_value;
      }

      best_x_items_from_asc_stacks_from_the_left[indirect_stack_id].push_back(the_best_stack_id);
    }
  }

  // and the same for choosing from the right from ID
  for (int number_of_pancakes = 1; number_of_pancakes < m; number_of_pancakes++) {
    // we need from the right, so we look from the end (iterate from the end)
    int the_best_stack_id = asc_stacks_ids_sorted_from_the_biggest[asc_stacks_ids_sorted_from_the_biggest.size() - 1];
    for (int indirect_stack_id = asc_stacks_ids_sorted_from_the_biggest.size() - 1; indirect_stack_id >= 0; indirect_stack_id--) {
      int temp_stack_id = asc_stacks_ids_sorted_from_the_biggest[indirect_stack_id];
      // indices shift again, in stacks sum starting from 0, so need to decrease 1...
      if (stacks_sums[temp_stack_id][number_of_pancakes - 1] > stacks_sums[the_best_stack_id][number_of_pancakes - 1]) {
        the_best_stack_id = temp_stack_id;
      }
      best_x_items_from_asc_stacks_from_the_right[indirect_stack_id].push_back(the_best_stack_id);
    }
  }

  // printf("DUMP LEFT\n");
  // for (int i = 0; i < best_x_items_from_asc_stacks_from_the_left.size(); i++) {
  //   for (int j = 1; j < m; j++) {
  //     printf("%d ", best_x_items_from_asc_stacks_from_the_left[i][j]);
  //   }
  //   printf("\n");
  // }

  // printf("DUMP RIGHT\n");
  // for (int i = 0; i < best_x_items_from_asc_stacks_from_the_right.size(); i++) {
  //   for (int j = 1; j < m; j++) {
  //     printf("%d ", best_x_items_from_asc_stacks_from_the_right[i][j]);
  //   }
  //   printf("\n");
  // }

  // now I need to find the biggest sum
  // I will choose 0, 1, 2, ... ascending stacks;
  // then for each choosen number of stacks I will choose 0, 1, 2, ..., m-1 first items from selected ascending stack
  // (both: from the left - so already chosen - more complex - and from the right);
  // and remaining number will be filled by pancakes from the big pile
  long long the_best_sum = 0LL;
  long long sum_of_all_chosen_asc_stacks = 0LL;
  for (int number_of_asc_stacks = 0; number_of_asc_stacks <= asc_stacks_ids_sorted_from_the_biggest.size(); number_of_asc_stacks++) {

    // printf("STARTING ITERATION number_of_asc_stacks=%d\n", number_of_asc_stacks);

    // if we crossed maximum legal number of pancakces, then break the loop
    if (number_of_asc_stacks * m > k) {
      break;
    }

    // prepare IDs, values
    int indirect_stack_id = number_of_asc_stacks - 1; // for 0 it will be -1...
    if (number_of_asc_stacks > 0) {
      int newly_added_stack_id = asc_stacks_ids_sorted_from_the_biggest[indirect_stack_id];
      long long sum_of_pancakes_from_the_newly_added_stack = stacks_sums[newly_added_stack_id][m - 1];

      // increase sum of all chosen ascending stacks
      sum_of_all_chosen_asc_stacks += sum_of_pancakes_from_the_newly_added_stack;
    }

    // if number of selected ascending stacks is maximized, then we cannot select additional pancakes from ascending stacks
    if (number_of_asc_stacks < asc_stacks_ids_sorted_from_the_biggest.size()) {
      // iterate over 0, 1, 2, ..., m-1 first additional pancakes from the selected stack from the right (easier)
      for (int number_of_extra_asc_pancakes = 1; number_of_extra_asc_pancakes < m; number_of_extra_asc_pancakes++) {
        int selected_extra_stack_id = best_x_items_from_asc_stacks_from_the_right[indirect_stack_id + 1][number_of_extra_asc_pancakes];
        long long sum_from_extra_asc_pancakes = stacks_sums[selected_extra_stack_id][number_of_extra_asc_pancakes - 1]; // indices shift, starting from 0...
        int remaining_pancakes_to_add = k - number_of_asc_stacks * m - number_of_extra_asc_pancakes;

        // if we crossed the number of maximum pancakes, then break
        if (remaining_pancakes_to_add < 0) {
          break;
        }

        // if we do not have enough pancakes to fill the remaining number from the big pile, then continue (there will be other combination)
        if (remaining_pancakes_to_add > all_pancakes_from_desc_stacks_sums.size()) {
          continue;
        }

        // sum coming from the remaining pancakes (from the big pile)
        long long sum_from_remaining_desc_pancakes = 0LL;
        if (remaining_pancakes_to_add > 0) { // reach out to array only if we have at least 1 remaining pancake to add!
          sum_from_remaining_desc_pancakes = all_pancakes_from_desc_stacks_sums[remaining_pancakes_to_add - 1]; // indices shift, starting from 0...
        }

        // check if the new sum is greater than the current best
        long long new_sum = sum_of_all_chosen_asc_stacks + sum_from_extra_asc_pancakes + sum_from_remaining_desc_pancakes;
        if (new_sum > the_best_sum) {
          the_best_sum = new_sum;
        }
      }

      // iterate over 0, 1, 2, ..., m-1 first additional pancakes from the selected stack from the left (swap needed!)
      if (number_of_asc_stacks > 0) { // it makes sense only if we selected already at least 1 stack
        for (int number_of_extra_asc_pancakes = 1; number_of_extra_asc_pancakes < m; number_of_extra_asc_pancakes++) {
          int selected_extra_stack_id = best_x_items_from_asc_stacks_from_the_left[indirect_stack_id][number_of_extra_asc_pancakes];
          long long sum_from_extra_asc_pancakes = stacks_sums[selected_extra_stack_id][number_of_extra_asc_pancakes - 1]; // indices shift, starting from 0...
          int remaining_pancakes_to_add = k - number_of_asc_stacks * m - number_of_extra_asc_pancakes;

          // if we crossed the number of maximum pancakes, then break
          if (remaining_pancakes_to_add < 0) {
            break;
          }

          // if we do not have enough pancakes to fill the remaining number from the big pile, then continue (there will be other combination)
          if (remaining_pancakes_to_add > all_pancakes_from_desc_stacks_sums.size()) {
            continue;
          }

          // now selected stack was already added, so we need to decrease its total sum
          long long sum_from_asc_stack_to_decrease = stacks_sums[selected_extra_stack_id][m - 1];

          // and we need to add, instead of that, the next biggest, unsued asc stack
          int replacement_stack_id = asc_stacks_ids_sorted_from_the_biggest[indirect_stack_id + 1];
          long long sum_from_the_replacement_asc_stack = stacks_sums[replacement_stack_id][m - 1];

          // sum coming from the remaining pancakes (from the big pile)
          long long sum_from_remaining_desc_pancakes = 0LL;
          if (remaining_pancakes_to_add > 0) { // reach out to array only if we have at least 1 remaining pancake to add!
            sum_from_remaining_desc_pancakes = all_pancakes_from_desc_stacks_sums[remaining_pancakes_to_add - 1]; // indices shift, starting from 0...
          }

          // check if the new sum is greater than the current best
          long long new_sum = sum_of_all_chosen_asc_stacks + sum_from_extra_asc_pancakes - sum_from_asc_stack_to_decrease + sum_from_the_replacement_asc_stack + sum_from_remaining_desc_pancakes;
          if (new_sum > the_best_sum) {
            the_best_sum = new_sum;
          }
        }
      }
    }

    // cover the case where we choose 0 extra pancakes from ascending stacks
    int remaining_pancakes_to_add = k - number_of_asc_stacks * m;
    if (remaining_pancakes_to_add >= 0) {
      if (remaining_pancakes_to_add <= all_pancakes_from_desc_stacks_sums.size()) {
        // sum coming from the remaining pancakes (from the big pile)
        long long sum_from_remaining_desc_pancakes = 0LL;
        if (remaining_pancakes_to_add > 0) { // reach out to array only if we have at least 1 remaining pancake to add!
          sum_from_remaining_desc_pancakes = all_pancakes_from_desc_stacks_sums[remaining_pancakes_to_add - 1]; // indices shift, starting from 0...
        }
        
        // check if the new sum is greater than the current best
        long long new_sum = sum_of_all_chosen_asc_stacks + sum_from_remaining_desc_pancakes;
        if (new_sum > the_best_sum) {
          the_best_sum = new_sum;
        }
      }
    }
  }

  // print the result!
  printf("%lld\n", the_best_sum);

  return 0;
}