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

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((i64)(x).size())

using namespace std;

#ifdef LOCAL
template<typename A, typename B>
auto&operator<<(auto&o,pair<A, B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<&","[!i++]<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

using i64 = long long;
using ll = i64;
using pii = pair<int, int>;
using pll = pair<i64, i64>;
using vi = vector<int>;
using vll = vector<i64>;

vll SolveStacksInc(vector<vll> stacks) {
	const i64 num_stacks = SZ(stacks);
	if (num_stacks == 0) { return vll{0}; }
	const i64 stack_height = SZ(stacks[0]);

	for (auto &stk : stacks) {
		stk.insert(stk.begin(), i64{0});
		for (i64 i = 1; i <= stack_height; ++i) {
			stk[i] += stk[i - 1];
		}
	}

	sort(ALL(stacks), [](const vll &lhs, const vll &rhs) {
		return lhs.back() > rhs.back();
	});
	debug(stacks);

	vll ans(num_stacks * stack_height + 1, -1);
	vector<multiset<i64>> opt_add_stack(stack_height + 1);
	vector<multiset<i64>> opt_repl_stack(stack_height + 1);

	for (const auto &stk : stacks) {
		for (i64 h = 0; h <= stack_height; ++h) {
			opt_add_stack[h].insert(stk[h]);
		}
	}

	i64 sum_stacks_added = 0;
	for (i64 num_full_stacks = 0; num_full_stacks < num_stacks; ++num_full_stacks) {
		const i64 next_stack_height = stacks[num_full_stacks].back();
		for (i64 h = 0; h <= stack_height; ++h) {
			i64 cand_add = -1, cand_repl = -1;
			if (!opt_add_stack[h].empty()) {
				cand_add = sum_stacks_added + *opt_add_stack[h].rbegin();
			}
			if (!opt_repl_stack[h].empty()) {
				cand_repl = sum_stacks_added + next_stack_height + *opt_repl_stack[h].rbegin();
			}
			const i64 cand_h = max(cand_add, cand_repl);
			const i64 where = num_full_stacks * stack_height + h;
			ans[where] = max(ans[where], cand_h);
		}

		const vll &stack_added = stacks[num_full_stacks];
		sum_stacks_added += next_stack_height;
		for (i64 h = 0; h <= stack_height; ++h) {
			opt_add_stack[h].erase(opt_add_stack[h].find(stack_added[h]));
			opt_repl_stack[h].insert(stack_added[h] - stack_added.back());
		}
	}

	return ans;
}

vll SolveStacksDec(const vector<vll> &stacks) {
	vll all_elems;
	for (const auto &stk : stacks) {
		copy(ALL(stk), back_inserter(all_elems));
	}
	sort(ALL(all_elems), greater<i64>());

	vll ans{0};
	for (i64 elem : all_elems) {
		ans.push_back(ans.back() + elem);
	}

	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(14);
	cerr << fixed << setprecision(6);

	i64 num_stacks, stack_height, k;
	cin >> num_stacks >> stack_height >> k;

	vector<vll> stacks_inc, stacks_dec;
	for (i64 i = 0; i < num_stacks; ++i) {
		vll stk(stack_height);
		for (i64 &x : stk) { cin >> x; }
		if (is_sorted(ALL(stk))) {
			stacks_inc.push_back(stk);
		} else {
			stacks_dec.push_back(stk);
		}
	}

	const vll opt_inc = SolveStacksInc(stacks_inc);
	debug(opt_inc);
	const vll opt_dec = SolveStacksDec(stacks_dec);
	debug(opt_dec);

	i64 ans = 0;
	for (i64 pos_inc = 0; pos_inc <= k; ++pos_inc) {
		const i64 pos_dec = k - pos_inc;
		if (pos_inc < SZ(opt_inc) && pos_dec < SZ(opt_dec)) {
			const i64 cand = opt_inc[pos_inc] + opt_dec[pos_dec];
			ans = max(ans, cand);
		}
	}

	cout << ans << "\n";
}