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
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include <cassert>
using namespace std;

#define FOR(i, n) for(int i = 0, __n = (n); i < __n; i++)

struct Stos {
  long long sum;
  vector<long long> s;

  bool operator<(const Stos& o) const {
    return sum < o.sum;
  }

  Stos(vector<long long> && v) : sum(0), s(std::move(v)) {
    for (auto &x : s) {
      sum += x;
    }
  }
};

int main() {
  int n, m; long long k;
  scanf("%d%d%lld", &n, &m, &k);

  vector<long long> G;
  vector<Stos> S;

  FOR(i, n) {
    vector<long long> s(m);
    FOR(j, m) {
      scanf("%lld", &s[j]);
    }

    if (std::is_sorted(s.begin(), s.end())) {
      S.push_back(Stos(std::move(s)));
    } else {
      G.insert(G.end(), s.begin(), s.end());
    }
  }

  sort(S.begin(), S.end());
  reverse(S.begin(), S.end());
  sort(G.begin(), G.end());
  reverse(G.begin(), G.end());

  vector<long long> Ssums(S.size()+1, 0);
  FOR(i, S.size()) {
    Ssums[i+1] = S[i].sum+Ssums[i];
    
  }
  vector<long long> Gsums(G.size()+1, 0);
  FOR(i, G.size()) {
    Gsums[i+1] = G[i] + Gsums[i];
  }

  long long best = 0;
  if(G.size() >= k) {
    best = Gsums[k];
  }

  FOR(i, S.size()) {
    // cerr << i << endl;
    if((i+1)*m <= k && k-(i+1)*m <= G.size()) {
      best = max(best, Ssums[i+1] + Gsums[k-(i+1)*m]);
    }
    // cerr << i << endl;
    long long acc = 0;
    FOR(j, S[i].s.size()) {
      acc += S[i].s[j];
      // cerr << i << " " << j <<endl;
      int pos = lower_bound(G.begin(), G.end(), S[i].s[j], greater<long long>()) - G.begin();
      int leftovers = k - pos - j - 1;

      if (leftovers < 0 || leftovers % m != 0) continue;

      int spos = leftovers / m;
      // cerr << "!" << spos << " " << Ssums.size() << " " << pos << " " << S[i].sum << " "  <<endl;
      if (spos < i) {
        best = max(best, Ssums[spos] + Gsums[pos] + acc);
      } else {
        if (spos+1 < Ssums.size()) {
          best = max(best, Ssums[spos+1] - S[i].sum + Gsums[pos] + acc);
        }
      }
    }
  }
  

  printf("%lld\n", best);

  return 0;
}