Submission #73158701

---

Source Code Expand

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())
MOD = 10**9+7
inf = 1<<64
from functools import lru_cache
def solve():
    n,m,k = mii()
    p = [lii() for i in range(n)]
    @lru_cache(None)
    def dfs(i,s):
        if s<0:
            return -inf
        if s<=0 or i>=n:
            return 0
        ans = 0
        for j in range(i+1,i+k+1):
            ans = max(ans,dfs(j,s-p[i][1])+p[i][0])
        return ans
    mx = 0
    for i in range(n):
        mx = max(mx,dfs(i,m))
    print(mx)

t = 1
# t = ii()
for _ in range(t):
    solve()

Submission Info

Judge Result