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

w=[]

v=[]

dp =[[0 for i in range(k+1)] for j in range(n+1)]



for i in range(n):

    a,b = list(map(int,input().split()))

    w.append(a)

    v.append(b)

for i in range(n):

    for sum_w in range(k+1):

        if sum_w - w[i] >=0:

            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])

        else:

            dp[i+1][sum_w]=dp[i][sum_w]



print((dp[-1][-1]))
N, W = list(map(int, input().split()))

a = []

for i in range(N):

    x,y = list(map(int,input().split()))

    a.append([x,y])

dp = [0]*(W+1)

max_weight = 0



for w, v in a:

    max_w = min(max_weight, W-w)

    for old_v, from_i in zip(dp[max_w::-1], list(range(max_w, -1, -1))):

        if dp[from_i+w] < old_v + v:

            dp[from_i+w] = old_v + v

    max_weight = min(max_weight+w, W)



print((max(dp)))

n, k = list(map(int, input().split()))
w = []
v = []
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(n):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k + 1):
        if sum_w - w[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]
print((dp[-1][-1]))

N, W = list(map(int, input().split()))
a = []
for i in range(N):
    x, y = list(map(int, input().split()))
    a.append([x, y])
dp = [0] * (W + 1)
max_weight = 0
for w, v in a:
    max_w = min(max_weight, W - w)
    for old_v, from_i in zip(dp[max_w::-1], list(range(max_w, -1, -1))):
        if dp[from_i + w] < old_v + v:
            dp[from_i + w] = old_v + v
    max_weight = min(max_weight + w, W)
print((max(dp)))

-n, k = list(map(int, input().split())) -w = [] -v = [] -dp = [[0 for i in range(k + 1)] for j in range(n + 1)] -for i in range(n): -    a, b = list(map(int, input().split())) -    w.append(a) -    v.append(b) -for i in range(n): -    for sum_w in range(k + 1): -        if sum_w - w[i] >= 0: -            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i]) -        else: -            dp[i + 1][sum_w] = dp[i][sum_w] -print((dp[-1][-1])) +N, W = list(map(int, input().split())) +a = [] +for i in range(N): +    x, y = list(map(int, input().split())) +    a.append([x, y]) +dp = [0] * (W + 1) +max_weight = 0 +for w, v in a: +    max_w = min(max_weight, W - w) +    for old_v, from_i in zip(dp[max_w::-1], list(range(max_w, -1, -1))): +        if dp[from_i + w] < old_v + v: +            dp[from_i + w] = old_v + v +    max_weight = min(max_weight + w, W) +print((max(dp)))