풀이

유명한 냅색 알고리즘을 통해서 dp 를 활용해 풀어주어야한다.

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

lst = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(k+1) for _ in range(n+1)]
mx = 0

for i in range(1, n+1):
    for j in range(1,k+1):
        if j >= lst[i-1][0]:
            dp[i][j] = max(lst[i-1][1]+dp[i-1][j-lst[i-1][0]], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])