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
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

#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(...) {}
#endif

#define x first
#define y second
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (ll i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)((x).size()))

using ll = long long;
using pii = pair<ll, ll>;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M, K;
  cin >> N >> M >> K;
  vec<vec<ll>> a(N, vec<ll>(M));
  vec<vec<ll>> asc, desc;

  rep (n, 0, N) {
    rep (m, 0, M) {
      cin >> a[n][m];
    }
  }

  rep (n, 0, N) {
    bool isdesc = 1;
    rep (m, 0, M-1) {
      if (a[n][m] < a[n][m+1]) isdesc = 0;
    }
    (isdesc ? desc : asc).push_back(a[n]);
  }
  vec<ll> descdp(M * desc.size() + 1);
  priority_queue<pii> pq;
  rep (m, 0, desc.size()) {
    reverse(all(desc[m]));
    pq.push({desc[m].back(), m});
    desc[m].pop_back();
  }
  rep (k, 0, sz(descdp)-1) {
    auto [val, idx] = pq.top();
    pq.pop();
    descdp[k+1] = descdp[k] + val;
    if (desc[idx].size()) {
      pq.push({desc[idx].back(), idx});
      desc[idx].pop_back();
    }
  }
  vec<multiset<ll>> bests(M+1);
  rep (m, 0, M+1) bests[m].insert(0);
  vec<vec<ll>> ascpref(asc.size());
  rep (k, 0, asc.size()) {
    ll s = 0;
    rep (m, 0, M+1) {
      bests[m].insert(s);
      ascpref[k].push_back(s);
      if (m < M)
        s += asc[k][m];
    }
  }
  sort(all(ascpref), [](auto& a, auto& b) {
    return a.back() > b.back();
  });

  vec<ll> rembest(M+1, ll(-2e18));
  int ascct = 0;
  ll best = 0;
  ll full = 0;
  auto f = [&](int m) {
    ll val = max(full + *bests[m].rbegin(), full + rembest[m] + *bests[M].rbegin());
    int descct = K - ascct;
    if (ir(descct, 0, sz(descdp)-1)) {
      best = max(best, val + descdp[descct]);
      debug(m, ascct, descct, val, descdp[descct], best);
    }
  };

  rep (k, 0, asc.size()) {
    debug(bests);
    rep (m, 0, M) {
      f(m);
      ascct++;
    }
    debug(ascct);

    rep (m, 0, M+1) {
      rembest[m] = max(rembest[m], ascpref[k][m] - ascpref[k][M]);
      bests[m].erase(bests[m].find(ascpref[k][m]));
    }
    full += ascpref[k][M];
  }
  f(0);
  debug(descdp);
  cout << best << "\n";
  return 0;
}