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
#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using ui = uint32_t;
using ll = int64_t;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, k; cin >> n >> m >> k;
  
  vector<vector<ll>> arr(n);
  priority_queue<tuple<ll, int, int>> pq;
  vector<int> stack_indices_sorted_by_sum;
  vector<ll> sums(n);

  vector<priority_queue<pair<ll, int>>> ranking_at_level(m);

  for(int i = 0; i < n; i++) {
    arr[i].resize(m);
    for(int j = 0; j < m; j++) {
      cin >> arr[i][j];
    }
    if(is_sorted(all(arr[i]))) { // 1, 1, 2, 3, 5
      stack_indices_sorted_by_sum.pb(i);
      sums[i] = reduce(all(arr[i]));
      ll sum = 0;
      for(int j = 0; j < m; j++) {
        sum += arr[i][j];
        ranking_at_level[j].push({ sum, i });
      }
    }
    else {
      // value, index, top_ind
      pq.push({ arr[i][0], i, 0 });
    }
  }

  int x = (int) pq.size();
  vector<ll> decreasing_choices_sum;
  decreasing_choices_sum.reserve(x * m + 1);
  decreasing_choices_sum.pb(0);

  while(!pq.empty()) {
    auto [ val, index, index_at_stack ] = pq.top(); pq.pop();
    decreasing_choices_sum.pb(val);
    if(index_at_stack != m - 1) {
      pq.push({ arr[index][index_at_stack + 1], index, index_at_stack + 1 });
    }
  }

  for(int i = 1; i <= x * m; i++) {
    decreasing_choices_sum[i] += decreasing_choices_sum[i - 1];
  }

  sort(all(stack_indices_sorted_by_sum), [&sums](int a, int b) {
    return sums[a] > sums[b];
  });

  ll res = 0;

  if(x * m >= k) {
    res = decreasing_choices_sum[k];
  }

  vector<bool> is_stack_deleted(n);
  ll whole_stacks_sum = 0;

  for(int taken_from_increasing = 1; taken_from_increasing <= min(k, (n - x) * m); taken_from_increasing++) {
    if(taken_from_increasing % m == 0) {
      int stacks_removed_so_far = taken_from_increasing / m;
      int deleted_stack_id = stack_indices_sorted_by_sum[stacks_removed_so_far - 1];
      whole_stacks_sum += sums[deleted_stack_id];
      is_stack_deleted[deleted_stack_id] = 1;
    }

    if(k - taken_from_increasing > x * m) {
      continue;
    }

    ll add = 0;

    if(taken_from_increasing % m != 0) {
      while(is_stack_deleted[ranking_at_level[(taken_from_increasing - 1) % m].top().second]) {
        ranking_at_level[(taken_from_increasing - 1) % m].pop();
      }
      if(taken_from_increasing % m != 0) {
        add = ranking_at_level[(taken_from_increasing - 1) % m].top().first;
      }
    }

    res = max(res, whole_stacks_sum + decreasing_choices_sum[k - taken_from_increasing] + add);
  }

  cout << res << '\n';

}