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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef long long LL;

// #define dprint(...) printf(__VA_ARGS__)
#define dprint(...)

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

  vector< LL > flipped;
  vector< vector<LL> > stacks(n);
  vector< vector<LL> > sums(n);

  for (int i=0; i<n; ++i) {
    stacks[i].resize(m);
    sums[i].resize(m+1, 0);
    
    for (int j=0; j<m; ++j) {
      scanf(" %lld", &stacks[i][j]);
      sums[i][j+1] = sums[i][j] + stacks[i][j];
    }
  }

  for (int i=n-1; i>=0; --i) {
    bool stop = false;
    for (int j=0; j<m-1; ++j) {
      if (stacks[i][j] < stacks[i][j+1]) stop = true;
    }
    if (stop) continue;
  
    for (LL s : stacks[i]) flipped.push_back(s);
    stacks[i] = stacks.back(); stacks.pop_back();
    sums[i] = sums.back(); sums.pop_back();
  }

  sort(flipped.begin(), flipped.end(), greater<LL>());
  vector<LL> flippedsum(flipped.size() + 1, 0);
  for (int i=0; i<flipped.size(); ++i) {
    flippedsum[i+1] = flippedsum[i] + flipped[i];
  }

  vector<int> beststacks;
  for (int i=0; i<stacks.size(); ++i) beststacks.push_back(i);
  sort(beststacks.begin(), beststacks.end(), [&](int a, int b) { return sums[a][m] > sums[b][m]; });

  dprint("Cale stosy:\n");
  for (int i: beststacks) {
    dprint("Stos %d: %lld\n", i, sums[i][m]);
  }

  LL result = 0;

  for (int i=0; i<m; ++i) {
    vector<int> best;
    for (int i=0; i<stacks.size(); ++i) best.push_back(i);
    sort(best.begin(), best.end(), [&](int a, int b) { return sums[a][i] > sums[b][i]; });

    for (int j: best) {
      dprint("Polowka %d: %lld\n", j, sums[j][i]);
    }
    
    int l = 0;
    int alti = 1;
    int curri = 0;
    int beststacki = 0;
    set<int> stacksset;
    LL stackssum = 0;

    for (int l=0; l<stacks.size(); ++l) {
      int rest = k - i - l*m;

      dprint("Rest: %d\n", rest);

      if (rest >= 0 && rest <= flipped.size()) {
        dprint("Polowka %d: %lld, odwrocone daja: %lld, stosy: %lld\n", best[curri], sums[best[curri]][i], flippedsum[rest], stackssum);
        result = max(result, flippedsum[rest] + sums[best[curri]][i] + stackssum);
      }

      if (l < stacks.size() - 1) {
        stacksset.insert(beststacks[beststacki]);
        stackssum += sums[beststacks[beststacki]][m];
        dprint("Dorzucam stos %d: %lld\n", beststacks[beststacki], sums[beststacks[beststacki]][m]); 
        ++beststacki;

        while (stacksset.find(best[curri]) != stacksset.end()) {
          dprint("Oo, kolizja\n");
          if (stacksset.find(best[alti]) != stacksset.end()) {
            if (sums[best[curri]][i] + sums[best[alti]][m] > sums[best[alti]][i] + sums[best[curri]][m]) {
              dprint("Pokonalem polowke: %d\n", best[alti]);
              ++alti;
            } else {
              dprint("Wskakuje polowka: %d\n", best[alti]);
              curri = alti;
              ++alti;
            }
          } else {
            if (sums[best[curri]][i] + sums[beststacks[beststacki]][m] > sums[best[alti]][i] + sums[best[curri]][m]) {
              ++alti;
              stacksset.insert(beststacks[beststacki]);
              stackssum += sums[beststacks[beststacki]][m];
              ++beststacki;
              
              dprint("Dorzucam stos: %d %lld\n", beststacks[beststacki], sums[beststacks[beststacki]][m]);
              dprint("Wyrzucam stos: %d %lld\n", best[curri], sums[best[curri]][m]);

              stacksset.erase(best[curri]);
              stackssum -= sums[best[curri]][m];
            } else {
              dprint("Wskakuje polowka (czysta): %d\n", best[alti]);
              curri = alti;
              ++alti;
            }
          }
        }
      }
    }
  }

  int rest = k - stacks.size() * m;
  if (rest >= 0 && rest <= flipped.size()) {
    LL stackssum = 0;
    for (int i=0; i<stacks.size(); ++i) {
      stackssum += sums[i][m];
    }
    result = max(result, flippedsum[rest] + stackssum);
  }

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

  return 0;
}