DPL_1_B – 0,1ナップザック問題

N, W = map(int,input().split())
value = []
weight = []
for i in range(N):
    va,we = map(int,input().split())
    value.append(va)
    weight.append(we)

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if (j - weight[i] >= 0):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - weight[i]] + value[i])
    
        dp[i + 1][j] = max(dp[i + 1][j] , dp[i][j])
    
print(dp[N][W])