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
import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())

pref = []

for _ in range(n):
    a = list(map(int, input().split()))
    
    p = [0] * (m + 1)
    for i in range(m):
        p[i+1] = p[i] + a[i]
    
    pref.append(p)

dp = [0] * (k + 1)

for i in range(n):
    ndp = dp[:]
    
    for w in range(1, m + 1):
        for j in range(k, w - 1, -1):
            ndp[j] = max(ndp[j], dp[j - w] + pref[i][w])
    
    dp = ndp

print(dp[k])