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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct StackData {
	bool nondecreasing = false; 
	int m = 0;
	long long sum = 0;
	vector<long long> a;    
	vector<long long> pref; 
};

struct EvalResult {
	long long value = 0;
	int count = 0;       
};

static pair<long long, int> best_for_stack(const StackData& st, long long p) {
	if (st.nondecreasing) {
		long long full = st.sum - p * st.m;
		if (full >= 0) {
			return {full, st.m};
		}
		return {0LL, 0};
	}

	int l = 0, r = st.m;
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (st.a[mid - 1] >= p) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	int x = l;
	long long val = st.pref[x] - p * x;
	return {val, x};
}

static EvalResult evaluate(const vector<StackData>& stacks, long long p) {
	EvalResult res;
	for (const StackData& st : stacks) {
		auto [v, c] = best_for_stack(st, p);
		res.value += v;
		res.count += c;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	vector<StackData> stacks(n);

	for (int i = 0; i < n; ++i) {
		vector<long long> row(m);
		for (int j = 0; j < m; ++j) {
			cin >> row[j];
		}

		bool nondec = true;
		for (int j = 1; j < m; ++j) {
			if (row[j - 1] > row[j]) {
				nondec = false;
				break;
			}
		}

		StackData st;
		st.nondecreasing = nondec;
		st.m = m;
		st.pref.assign(m + 1, 0);
		for (int j = 0; j < m; ++j) {
			st.pref[j + 1] = st.pref[j] + row[j];
		}
		st.sum = st.pref[m];

		if (!nondec) {
			st.a = move(row);
		}

		stacks[i] = move(st);
	}

	const long long MAX_A = 1000000000000LL;
	long long lo = 0, hi = MAX_A + 1;

	while (lo < hi) {
		long long mid = (lo + hi + 1) / 2;
		EvalResult cur = evaluate(stacks, mid);
		if (cur.count >= k) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}

	EvalResult at_lo = evaluate(stacks, lo);
	long long answer = at_lo.value + lo * 1LL * k;
	cout << answer << '\n';
	return 0;
}