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
#include <cstdio>
#include <vector>
#include <algorithm>
using std::vector;

const int M = 301'013;
const int Q = 1'000'000'007;

int n, m, k;
vector<long long> v[M], t, st, sv[M];
vector<std::pair<long long, long long> > e;

int main() {
  scanf("%d %d %d", &n, &m, &k);
  int n1 = 0;
  for (int ii = 0; ii < n; ii++) {
    v[n1] = vector<long long>(m);
    for (int j = 0; j < m; j++)
      scanf("%lld", &v[n1][j]);
    if (v[n1][0] >= v[n1][m-1]) {
      for (int j = 0; j < m; j++)
        t.push_back(v[n1][j]);
    } else {
      sv[n1] = vector<long long>(m+1);
      for (int j = 0; j < m; j++)
        sv[n1][j+1] = sv[n1][j] + v[n1][j];
      n1++;
    }
  }
  std::sort(t.begin(), t.end());
  std::reverse(t.begin(), t.end());
  st = vector<long long>(t.size()+1);
  for (int i = 0; i < t.size(); i++) {
    st[i+1] = st[i] + t[i];
  }
  if (!n1) {
    printf("%lld\n", st[k]);
    return 0;
  }
  long long ret = 0;
  for(int r = 0; r < m && r <= k; r++) {
    int u = (k - r) % m;
    if (u > t.size()) continue;
    int pel = (k - r - u) / m;
    int n2 = (t.size() - u) / m;
    if (pel > n1+n2) continue;
    if (pel == n1+n2 && r > 0) continue;
    e.clear();
    for (int i = 0; i < n1; i++) {
      e.push_back(std::make_pair(sv[i].back(), sv[i][r]));
    }
    for (int i = 0; i < n2; i++) {
      e.push_back(std::make_pair(st[(i+1)*m+u] - st[i*m+u], -1LL));
    }
    std::sort(e.begin(), e.end());
    std::reverse(e.begin(), e.end());
    long long w = st[u];
    for (int i = 0; i < pel; i++) w += e[i].first;
    if (!r) {
      ret = std::max(ret, w);
      continue;
    }
    for (int i = 0; i < e.size(); i++) if (e[i].second >= 0) {
      if (i >= pel) ret = std::max(ret, w + e[i].second);
      else ret = std::max(ret, w + e[i].second + e[pel].first - e[i].first);
    }
  }
  printf("%lld\n",ret);
  return 0;
}