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
n, m, k = map(int, input().split())
odwrocone = []
normalne = []
for i in range(n):
    stos = list(map(int, input().split()))
    if m == 1:
        for panc in stos:
            odwrocone.append(panc)
    else:
        if stos[0] < stos[-1]:
            normalne.append(stos)
        else:
            for panc in stos:
                odwrocone.append(panc)
wielod = len(odwrocone)
wielnor = len(normalne) * m
maxi = 0
odwrocone.sort(reverse=True)
normalne.sort(key=sum, reverse=True)
for i in range(1, wielod):
    odwrocone[i] += odwrocone[i - 1]
bestod = [0 for _ in range(k + 1)]
for i in range(1, k + 1):
    if wielod < i:
        bestod[i] = bestod[i - 1]
    else:
        bestod[i] = odwrocone[i - 1]
if wielnor == 0:
    res = bestod[k]
    print(res)
    exit()
prefixes = [[0 for _ in range(len(normalne))] for _ in range(m + 1)]
for i in range(len(normalne)):
    prefixes[1][i] = normalne[i][0]
for i in range(2, m + 1):
    for j in range(len(normalne)):
        prefixes[i][j] = prefixes[i - 1][j] + normalne[j][i - 1]
sumanaprefixach = [0 for _ in range(len(normalne) + 1)]
for p in range(1, len(normalne) + 1):
    sumanaprefixach[p] = prefixes[-1][p - 1] + sumanaprefixach[p - 1]
sufixmax = [[0 for _ in range(len(normalne))] for s in range(m + 1)]
sufixmin = [[1e9 for _ in range(len(normalne))] for s in range(m + 1)]
for i in range(m + 1):
    sufixmax[i][-1] = prefixes[i][-1]
    sufixmin[i][0] = prefixes[-1][0] - prefixes[i][0]
    for j in range(len(normalne) - 2, -1, -1):
        sufixmax[i][j] = max(sufixmax[i][j + 1], prefixes[i][j])
    for j in range(1, len(normalne)):
        sufixmin[i][j] = min(sufixmin[i][j - 1], prefixes[-1][j] - prefixes[i][j])
res = 0
for c in range(0, k + 1):
    tmp = k - c
    if c < wielnor:
        bestnorm = max(sumanaprefixach[c // m] + sufixmax[c % m][c // m],sumanaprefixach[(c // m) + 1] - sufixmin[c % m][c // m])
        res = max(bestnorm + bestod[k - c], res)
    else:
        bestnorm = sumanaprefixach[-1]
        res = max(bestnorm + bestod[k - c], res)
print(res)