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
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <functional>
#include <numeric>
#define rep(i, p, k) for (int i = (p); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define fi first
#define sc second
#ifndef DEBUG
#define debug(...)
#else
#include "debug.h"
#endif
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<ll> s;
  s.push_back(0);
  vector<vector<ll>> in(n, vector<ll>(m));
  vector<vector<pair<ll, int>>> st(m);
  vector<ll> b(m, INT64_MIN);
  vector<pair<ll, int>> sums;
  for (auto &V : st)
    V.reserve(n);
  for (int i = 0; i < n; i++) {
    for (auto &v : in[i])
      cin >> v;
    if (is_sorted(all(in[i]), greater{})) {
      for (auto v : in[i])
        s.push_back(v);
    } else {
      ll ss = 0;
      rep(j, 0, m) {
        st[j].emplace_back(ss, i);
        ss += in[i][j];
      }
      sums.emplace_back(ss, i);
    }
  }
  sort(1 + all(s), greater{});
  partial_sum(all(s), s.begin());
  for (auto &V : st)
    sort(all(V));
  sort(all(sums));
  ll psum = 0;
  ll res = 0;
  int sss = int(m * sums.size());
  vector<bool> done(n, false);
  for (int i = 0; i < sss; i++) {
    int rr = i % m;
    if (i <= k && k - i < (int)s.size()) {
      auto &c = st[rr];
      while (done[c.back().second])
        c.pop_back();
      ll tr = psum + c.back().first;
      res = max(res, tr + s[k - i]);
      if (rr)
        res = max(res, psum + sums.back().first + b[rr] + s[k - i]);
    }
    if (rr == m - 1) {
      auto [S, ind] = sums.back();
      psum += S;
      done[ind] = true;
      ll pre = 0;
      rep(j, 1, m) {
        pre += in[ind][j-1];
        b[j] = max(b[j], pre - S);
      }
      sums.pop_back();
    }
  }
  if (sss <= k && k - sss < (int)s.size())
    res = max(res, psum + s[k - sss]);
  cout << res << '\n';
}