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

using int64 = long long int;

int main()
{
    int n, m, k;
    std::cin >> n >> m >> k;
    const int min_mk = m < k ? m : k;
    std::vector<std::vector<int64>> a(n, std::vector<int64>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
			std::cin >> a[i][j];
    // dp[j] - maks suma uzywajac pierwszych i stosów + wybierajac j nalesnikow
    std::vector<int64> dps[2] = {std::vector<int64>(k, 0), std::vector<int64>(k, 0)};
	std::vector<int64> prefixes(m);
    for (int i = 0; i < n; ++i)
    {
		for (int j = 0; j < m; ++j)
			prefixes[j] = a[i][j] + (j > 0 ? prefixes[j - 1] : 0);
        std::vector<int64>& dp = dps[i & 1];
        const std::vector<int64>& prev_dp = dps[(i + 1) & 1];
        const int j_end = std::min(k, (i + 1) * m);
        for (int j = 0; j < j_end; ++j)
        {
            int64 max = prev_dp[j];
            const int l_start = std::max(0, j - i * m);
            const int l_end = std::min(j + 1, min_mk);
            for (int l = l_start; l < l_end; ++l)
            {
                const int prev_idx = j - l - 1;
				const int64 val = (prev_idx >= 0 ? prev_dp[prev_idx] : 0) + prefixes[l];
				if (val > max)
					max = val;
			}
            dp[j] = max;
        }
    }
    const int64 result = dps[(n - 1) & 1].back();
    std::cout << result;
    return 0;
}

/*

1 3 3
5 5 5


2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999



3 3 5
1 2 3
1 2 3
3 2 1



3 3 3
1 2 3
1 2 10
3 2 1


*/