4 7
2 3
3 4
4 5
5 6

9

n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
dp = [0] * (W+1)
for wt, val in items:
    for w in range(W, wt-1, -1):
        dp[w] = max(dp[w], dp[w-wt]+val)
print(dp[W])