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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

int main() {
  cin.tie(0)->sync_with_stdio(0);
  
  int n, m, k;
  cin >> n >> m >> k;
  vector<ll> decr;
  vector<vector<ll>> incr;
  vector<pair<ll, int>> ind;
  for(int i = 0; i < n; i++) {
    vector<ll> a(m);
    bool f = 0;
    for(int j = 0; j < m; j++) {
      cin >> a[j];
      if(j && a[j] < a[j - 1]) f = 1;
    }
    if(f) {
      decr.insert(decr.end(), all(a));
    } else {
      incr.push_back(a);
      ll s = accumulate(all(a), 0LL);
      ind.push_back({s, ind.size()});
    }
  }
  sort(decr.rbegin(), decr.rend());
  decr.insert(decr.begin(), 0);
  for(int i = 1; i < decr.size(); i++) {
    decr[i] += decr[i - 1];
  }
  
  sort(ind.rbegin(), ind.rend());
  vector<vector<ll>> tmp = incr;
  for(int i = 0; i < incr.size(); i++) {
    incr[i] = tmp[ind[i].second];
  }
  n = incr.size();
  vector<ll> pre(n + 1);
  for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + ind[i - 1].first;
  
  vector<vector<ll>> aft(n + 1, vector<ll>(m));
  for(int i = n; i >= 1; i--) {
    for(int j = 1; j < m; j++) {
      aft[i][j] = aft[i][j - 1] + incr[i - 1][j - 1];
    }
    if(i < n) {
      for(int j = 0; j < m; j++) {
        aft[i][j] = max(aft[i][j], aft[i + 1][j]);
      }
    }
  }
  vector<vector<ll>> bef(n + 1, vector<ll>(m));
  for(int i = 1; i <= n; i++) {
    bef[i][m - 1] = incr[i - 1][m - 1];
    for(int j = m - 2; j >= 0; j--) {
      bef[i][j] = bef[i][j + 1] + incr[i - 1][j];
    }
    if(i > 1) {
      for(int j = 0; j < m; j++) {
        bef[i][j] = min(bef[i][j], bef[i - 1][j]);
      }
    }
  }
  
  vector<ll> res(min(k, n * m) + 1);
  for(int i = 0; i < res.size(); i++) {
    int full = i / m;
    int rem = i % m;
    if(full == n) res[i] = pre[full];
    else {
      res[i] = pre[full] + aft[full + 1][rem];
      res[i] = max(res[i], pre[full + 1] - bef[full + 1][rem]);
    }
  }

  ll ans = 0;
  for(int i = 0; i <= k; i++) {
    if(i < decr.size() && k - i < res.size()) {
      ans = max(ans, decr[i] + res[k - i]);
    }
  }
  cout << ans << endl;
}