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

int main()
{
	long long n, m, k;

	cin >> n >> m >> k;

	vector<vector<long long>> stacks;

	for (long long i = 0; i < n; i++)
	{
		vector<long long> temp;

		for (long j = 0; j < m; j++)
		{
			long long x;
			cin >> x;
			temp.push_back(x);
		}

		stacks.push_back(temp);
	}

	long long maxK = 0;
	long long maxStack = 0;

	long long maxFirst = 0;

	if (k <= m)
	{
		for (long long j = 0; j < stacks.size(); j++)
		{
			long long sum = accumulate(stacks[j].begin(), stacks[j].begin() + k, 0);
			if (sum > maxFirst) {
				maxFirst = sum;
			}
		}
	}

	for (long long i = 0; i < k; i++)
	{
		long long max = 0;
		long long index = -1;

		for (long long j = 0; j < stacks.size(); j++)
		{
			if (stacks[j].size() > 0 && stacks[j][0] > max)
			{
				max = stacks[j][0];
				index = j;
			}
		}

		maxK += max;
		stacks[index].erase(stacks[index].begin());

		if (k - m == i + 1)
		{
			for (long long j = 0; j < stacks.size(); j++)
			{
				long long sum = accumulate(stacks[j].begin(), stacks[j].end(), 0);
				if (sum + maxK > maxStack) {
					maxStack = sum + maxK;
				}
			}
		}


	}

	cout << max(maxFirst, max(maxK, maxStack));
}