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
import sys


data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)

n = next(it)
m = next(it)
k = next(it)

stacks = []
max_a = 0

for _ in range(n):
    arr = [next(it) for _ in range(m)]
    ma = max(arr)
    if ma > max_a:
        max_a = ma
    stacks.append(arr)

def evaluate(lam: int):
    total_best = 0
    total_cnt = 0

    for arr in stacks:
        s = 0
        best = 0
        best_t = 0
        t = 0

        for x in arr:
            t += 1
            s += x - lam
            if s > best:
                best = s
                best_t = t
            elif s == best and t > best_t:
                best_t = t

        total_best += best
        total_cnt += best_t
    return total_best, total_cnt

lo, hi = 0, max_a + 1
best_lam = 0

while lo <= hi:
    mid = (lo + hi) // 2
    _, cnt = evaluate(mid)
    if cnt >= k:
        best_lam = mid
        lo = mid + 1
    else:
        hi = mid - 1
best_val, _ = evaluate(best_lam)
ans = best_val + best_lam * k
print(ans)