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
#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>
using namespace std;

struct sum_range {
  int n;
  vector<int> values;
  sum_range(const vector<int> &content) {
    n = content.size();
    values.resize(n + 1);
    for (int i = 1; i <= n; i++)
      values[i] = values[i - 1] + content[i - 1];
  }

  sum_range(const vector<pi> &content) {
    n = content.size();
    values.resize(n + 1);
    for (int i = 1; i <= n; i++)
      values[i] = values[i - 1] + content[i - 1].first;
  }

  int query(int l, int r) { //[l r)
    if (r <= l)
      return 0;
    r = min(r, n);
    l = max(l, 0LL);
    return values[r] - values[l];
  }
};

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int _n, m, k;
  cin >> _n >> m >> k;
  vector<int> free;
  vector<vector<int>> increasing;
  vector<vector<pi>> increasing_and_rest_offset(m);
  while (_n--) {
    vector<int> stos(m);
    int suma = 0;
    for (auto &nalesnik : stos) {
      cin >> nalesnik;
      suma += nalesnik;
    }

    if (stos[0] < stos.back()) {
      for(auto &iaro : increasing_and_rest_offset)
        iaro.push_back({suma, increasing.size()});
      increasing.push_back(stos);
    } else
      while (stos.size()) {
        auto tmp = stos.back();
        stos.pop_back();
        free.push_back(tmp);
      }
  }
  sort(free.rbegin(), free.rend());
  sum_range Sfree(free);
  for(int offset = 0; offset < m; offset++){
    for(int l = offset; l+m-1<free.size(); l+=m){
      int sum = 0;
      increasing_and_rest_offset[offset].push_back({Sfree.query(l, l+m), INT_MAX});
    }
    sort(increasing_and_rest_offset[offset].rbegin(), increasing_and_rest_offset[offset].rend());
  }


  vector<sum_range> SR;
  for(auto iaro : increasing_and_rest_offset)
    SR.push_back(sum_range(iaro));

  int res=Sfree.query(0, k);
  for(int i=0; i<increasing.size(); i++){
    int current_sum=0;
    int row_sum=0;
    for(auto r : increasing[i]) row_sum+=r;

    for(int j=0; j<=m;j++){
      //[0,j)]
      int pancakes_left = k-j;
      if(pancakes_left<0) break;

      int m_offset = pancakes_left%m;
      int set_cnt = (pancakes_left-m_offset)/m;
      int current_res=0;
      if(set_cnt == 0){
        current_res = current_sum + Sfree.query(0, m_offset);
      } else{
        if(set_cnt >= increasing_and_rest_offset[m_offset].size()) goto add;
        
        int tmp;// = SR[m_offset].query(0, set_cnt);
        if(increasing_and_rest_offset[m_offset][set_cnt-1] > make_pair(row_sum, i)) tmp = SR[m_offset].query(0, set_cnt);
        else tmp = SR[m_offset].query(0, set_cnt+1)-row_sum;
        
        current_res = current_sum + tmp + Sfree.query(0, m_offset);
      }

      res=max(res, current_res);
      add:
      if(j<m) current_sum+=increasing[i][j];
    }
  }
  cout << res << '\n';
}