N,W = [int(i) for i in input().split()]

w = [] # limit weight to knapsack capacity

v = [] # maximize value

for i in range(N):

  line = input().split()

  w.append(int(line[0]))

  v.append(int(line[1]))

mem = [[0]*(W+1) for i in range(N)]

for i in range(w[0], W+1):

  mem[0][i] = v[0]

for i in range(1, N):

  for j in range(1, W+1):

    if w[i] > j:

      mem[i][j] = mem[i-1][j]

    else:

      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])

#print(mem)

print(("%s" % mem[N-1][W]))
N,W = [int(i) for i in input().split()]

dp = [0 for i in range(W+1)] # dp[i] is the the max value you have achieve with weight i

for i in range(N):

  w,value = [int(i) for i in input().split()]

  for weight in range(W-w, -1, -1): # range of kanpsack weight in which i can push the current item

    dp[weight + w] = max(dp[weight + w], dp[weight] + value)

print(("%s" % dp[W]))
N, W = [int(i) for i in input().split()]
w = []  # limit weight to knapsack capacity
v = []  # maximize value
for i in range(N):
    line = input().split()
    w.append(int(line[0]))
    v.append(int(line[1]))
mem = [[0] * (W + 1) for i in range(N)]
for i in range(w[0], W + 1):
    mem[0][i] = v[0]
for i in range(1, N):
    for j in range(1, W + 1):
        if w[i] > j:
            mem[i][j] = mem[i - 1][j]
        else:
            mem[i][j] = max(mem[i - 1][j], v[i] + mem[i - 1][j - w[i]])
# print(mem)
print(("%s" % mem[N - 1][W]))

N, W = [int(i) for i in input().split()]
dp = [
    0 for i in range(W + 1)
]  # dp[i] is the the max value you have achieve with weight i
for i in range(N):
    w, value = [int(i) for i in input().split()]
    for weight in range(
        W - w, -1, -1
    ):  # range of kanpsack weight in which i can push the current item
        dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print(("%s" % dp[W]))

-w = []  # limit weight to knapsack capacity -v = []  # maximize value +dp = [ +    0 for i in range(W + 1) +]  # dp[i] is the the max value you have achieve with weight i -    line = input().split() -    w.append(int(line[0])) -    v.append(int(line[1])) -mem = [[0] * (W + 1) for i in range(N)] -for i in range(w[0], W + 1): -    mem[0][i] = v[0] -for i in range(1, N): -    for j in range(1, W + 1): -        if w[i] > j: -            mem[i][j] = mem[i - 1][j] -        else: -            mem[i][j] = max(mem[i - 1][j], v[i] + mem[i - 1][j - w[i]]) -# print(mem) -print(("%s" % mem[N - 1][W])) +    w, value = [int(i) for i in input().split()] +    for weight in range( +        W - w, -1, -1 +    ):  # range of kanpsack weight in which i can push the current item +        dp[weight + w] = max(dp[weight + w], dp[weight] + value) +print(("%s" % dp[W]))