CodeEff/ECCO huggingface dataset:
# Original solution
def knapsack(n,w,wts,vals):
    if n==0 or w==0:
        return 0
    inc,exc=-1,-1
    if wts[n-1]<=w:
        inc= vals[n-1]+ knapsack(n-1,w-wts[n-1],wts,vals)
    exc= knapsack(n-1,w,wts,vals)

    return max(inc,exc)

n,w=list(map(int,input().split()))
wts,vals=[],[]
for i in range(n):
    a,b=list(map(int,input().split()))
    wts.append(a)
    vals.append(b)

print((knapsack(n,w,wts,vals)))


# Optimized solution
def knapsack_dp(n,w,wts,val):
    dp=[[0]*(w+1) for i in range(n+1)]

    for i in range(n+1):
        for j in range(w+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif wts[i-1]<=j:
                dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wts[i-1]])
            else:
                dp[i][j]=dp[i-1][j]

    return dp[n][w]


n,w=list(map(int,input().split()))
wts,vals=[],[]
for i in range(n):
    a,b=list(map(int,input().split()))
    wts.append(a)
    vals.append(b)

print((knapsack_dp(n,w,wts,vals)))
# Original solution
N, W = list(map(int, input().split()))

weights = [0]*(N+10)
values = [0]*(N+10)

dp = [[0]*(W+10) for i in range(N+10)]

for i in range(N):
    weights[i], values[i] = list(map(int, input().split()))
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            dp[i+1][sum_w] = max(dp[i][sum_w-weights[i]]+values[i],
                                 dp[i+1][sum_w])
        else:
            dp[i+1][sum_w] = max(dp[i][sum_w],
                                 dp[i+1][sum_w])

print((max([max(row) for row in dp])))

# Optimized solution
N, W = list(map(int, input().split()))

weights = [0]*(N+5)
values = [0]*(N+5)

dp = [[0]*(W+5) for i in range(N+5)]

for i in range(N):
    weights[i], values[i] = list(map(int, input().split()))
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            if dp[i+1][sum_w] < dp[i][sum_w-weights[i]]+values[i]:
                dp[i+1][sum_w] = dp[i][sum_w-weights[i]]+values[i]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]


print((max([max(row) for row in dp])))
# Original solution
import sys
input = sys.stdin.readline

n, w = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが良い場合は値を更新

print((max(dp)))

# Optimized solution
n, w = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):#ある重さjについて
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが重さjでの価値が高い場合は値を更新

print((max(dp)))
# Original solution
MAX_N = 110
N, W = list(map(int, input().split()))
weight = [0] * MAX_N
value = [0] * MAX_N
for i in range(N):
    weight[i], value[i] = list(map(int, input().split()))
dp = [[0] * (W + 1) for _ in range(MAX_N)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - weight[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
# for l in dp:
#     print(l)
print((dp[N][W]))

# Optimized solution
MAX_N = 110
MAX_W = 10 ** 5 + 100
N, W = list(map(int, input().split()))
w = [0] * MAX_N
v = [0] * MAX_N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print((dp[N][W]))
# Original solution
N,W = list(map(int,input().split()))
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    w,v = list(map(int,input().split()))
    for j in range(W+1):
        if j < w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j-w]+v,dp[i][j])
print((dp[N][W]))

# Optimized solution
N,W = list(map(int, input().split()))
dp = [0]*(W+1)
for _ in range(N):
    w,v = list(map(int,input().split()))
    for i in range(W,-1,-1):
        if i-w < 0:
            continue
        dp[i] = max(dp[i], dp[i-w]+v)
print((max(dp)))
# Original solution
N, W = list(map(int, input().strip().split()))

values = []
weights = []

for _ in range(N):
    w, v = list(map(int, input().strip().split()))
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    curr_v = values[i]
    curr_w = weights[i]
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], curr_v + dp[w - curr_w])

print((dp[W]))

# Optimized solution
N, W = list(map(int, input().strip().split()))
 
values = []
weights = []
 
for _ in range(N):
    w, v = list(map(int, input().strip().split()))
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
print((dp[W]))
# Original solution
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
INF = 10**11+1
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print((max(dp[-1])))

# Optimized solution
N, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print((max(dp[-1])))
# Original solution
def solve():
  N, W = list(map(int, input().split()))
  weight = [0 for i in range(N)]
  value = [0 for i in range(N)]
  for i in range(N):
    weight[i], value[i] = list(map(int, input().split()))
  dp = [[0 for w in range(100100)] for i in range(110)]

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

  return dp[N][W]

print((solve()))


# Optimized solution
def solve():
    N, W = list(map(int, input().split()))
    weight = [0 for i in range(N)]
    value = [0 for i in range(N)]
    for i in range(N):
        weight[i], value[i] = list(map(int, input().split()))
    dp = [0 for w in range(W + 1)]

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for w in range(W, -1, -1):
            _w = w + wi
            _v = dp[w] + vi
            if _w > W: continue
            if _v <= dp[_w]: continue
            dp[_w] = _v
    return dp[-1]

print((solve()))
# Original solution
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = list(map(int, input().split()))
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = list(map(int, input().split()))
        for sum_w in range(W, w-1, -1):
            if sum_w - w >= 0:
                dp[sum_w] = max(dp[sum_w], dp[sum_w - w] + v)
    print((dp[-1]))

if __name__ == '__main__':
    main()


# Optimized solution
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = list(map(int, input().split()))
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = list(map(int, input().split()))
        for sum_w in range(W, w-1, -1):
            tv = dp[sum_w - w] + v
            if tv > dp[sum_w]:
                dp[sum_w] = tv
    print((dp[-1]))

if __name__ == '__main__':
    main()
# Original solution
x, y = list(map(int, input().split()))
dp = [[0]*(y+1) for _ in range(x+1)]

for i in range(1, x+1):
    w, v = list(map(int, input().split()))
    for j in range(y+1):
        num0 = dp[i-1][j]
        if j-w >= 0:
            num1 = dp[i-1][j-w]+v
            if num1 > num0:
                dp[i][j] = num1
            else:
                dp[i][j] = num0
        else:
            dp[i][j] = num0
print((max(dp[-1])))


# Optimized solution
def num():
    x, y = list(map(int, input().split()))
    dp = [0]*(y+1)

    for i in range(x):
        w, v = list(map(int, input().split()))
        for j in range(y, w-1, -1):
            num = dp[j-w]+v
            if num > dp[j]:
                dp[j] = num
    print((dp[-1]))

num()
# Original solution
n, w = list(map(int, input().split(' ')))
items = [[]] * n
for i in range(n):
  weight, val = list(map(int, input().split(' ')))
  items[i] = [weight, val]

# print(n, w)
# print(items)

dp = []
for i in range(n+1):
  dp.append([])
  for j in range(w+1):
  	dp[i].append(0)

# print(len(dp), len(dp[0]), dp[0][0])

for i in range(n):
  weight , val = items[i]
  for sum_w in range(w+1):
    # i番目のアイテムを選択する
    if sum_w - weight >= 0:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight] + val)
    # i番目のアイテムを選択しない
    dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print((dp[n][w]))

# Optimized solution
n, w = list(map(int, input().split()))
wl = [0] * n
vl = [0] * n
for i in range(n):
  wl[i], vl[i] = list(map(int, input().split()))

dp = [[]] * (n+1)
for i in range(n+1):
  dp[i] = [0] * (w+1)

for i in range(n):
  for j in range(w+1):
    if j >= wl[i]:
      dp[i+1][j] = max(dp[i][j], dp[i][j-wl[i]]+vl[i])
    dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print((dp[n][w]))
#for i in range(n+1):
#  print(dp[i])
# Original solution
import math
from decimal import *

n, w = list(map(int, input().split()))
cost, weights = [],[]
for i in range(n):
    a,b = list(map(int, input().split()))
    weights.append(a)
    cost.append(b)

def kp(pt, c, ans):
    if(pt==-1 or c==0):
        return ans
    else:
        var1, var2 = 0, 0
        var1= kp(pt-1, c, ans)
        if(c >= weights[pt]):
            var2 = cost[pt]+kp(pt-1, c-weights[pt], ans)
        ans = max(var1, var2)
    return ans
ans = kp(n-1, w, 0)
print(ans)

# Optimized solution
import math

n, w = list(map(int, input().split()))
weights = []
costs = []
for i in range(n):
    a,b = list(map(int, input().split()))
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w+1)] for i in range(n)]
for i in range(w+1):
    if(i>= weights[0]):
        dp[0][i] = costs[0]

for i in range(1, n):
    for j in range(w+1):
        if(j >= weights[i]):
            val = max(dp[i-1][j], costs[i]+dp[i-1][j-weights[i]])
            dp[i][j] = val
        else:
            dp[i][j] =max(dp[i][j], dp[i-1][j])
print((dp[-1][-1]))
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
 
dp = [-1 for _ in range(W + 1)] # dp[重量の総和]:= 価値の総和
dp[0] = 0
 
for i in range(N):
  w, v = wv[i]
  for j in range(W, -1, -1):
    if dp[j] >= 0 and j + w <=  W:
      dp[j+w] = max(dp[j+w], dp[j]+v)
      
print((max(dp)))

# Optimized solution
# 埋める配列
# dp[w] : 入っている重さがwのときの価値の最大値

# 計算方法
# dp[0][0] = 0
# dp[w] = max(dp[w - wi] + vi)

# 埋める順序
# 後ろから

N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)
for i in range(N):
    wi, vi = wv[i]
    for j in range(W, -1, -1):
        if j - wi >= 0:
            dp[j] = max(dp[j], dp[j - wi] + vi)
            
print((dp[-1]))
# Original solution
n, s = [int(i) for i in  input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in range(limit+1)] for _ in range(n)]

    prev = [0 for _ in range(limit+1)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            prev[w] = values[0]

    for i in range(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in range(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print((knapsack(weights, values, s)))

# Optimized solution
n, s = [int(i) for i in  input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in range(limit+1)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            prev[w] = values[0]

    for i in range(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in range(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print((knapsack(weights, values, s)))
# Original solution
INF = float('inf')

N, capW = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = {0: 0}
for wi, vi in items:
    for w, v in list(dp.items()):
        if w+wi <= capW:
            dp[w+wi] = max(dp.get(w+wi, 0), v+vi)

print((max(dp.values())))


# Optimized solution
N, capW = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(list(range(wi, capW+1))):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)

print((knapsack01(items, capW)))
# Original solution
N, capW = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(list(range(wi, capW+1))):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)

print((knapsack01(items, capW)))


# Optimized solution
N, capW = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        dp = [v1 if v1 >= v2 else v2 for v1, v2 in zip(dp, [0]*wi + [v+vi for v in dp[:capW-wi+1]])]
    return max(dp)

print((knapsack01(items, capW)))
# Original solution
import sys
import math
from  collections import defaultdict

sys.setrecursionlimit(1000000000)

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = list(map(int, input().split()))
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = list(map(int, input().split()))
	dp = {}
	ans = knapsack(wgt, val, 0, n, dp, w)
	print(ans)

def knapsack(wgt, val, i, n, dp, w):
	if (i, w) in dp:
		return dp[(i, w)]
	elif i >= n:
		return 0
	else:
		dp[(i, w)] = knapsack(wgt, val, i + 1, n, dp, w)
		if wgt[i] <= w:
			dp[(i, w)] = max(dp[(i, w)], val[i] + knapsack(wgt, val, i + 1, n, dp, w - wgt[i]))
		return dp[(i, w)]


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)


# Optimized solution
import sys
import math
from  collections import defaultdict


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = list(map(int, input().split()))
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = list(map(int, input().split()))
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if wgt[i - 1] <= j:
				dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wgt[i - 1]])
	ans = dp[-1][-1]
	print(ans)



if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1] * (W + 1) for _ in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print((rec(N, W)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, W = (int(i) for i in input().split())
    VW = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if 0 <= j - VW[i][0]:
                dp[i+1][j] = max(dp[i][j], dp[i][j - VW[i][0]] + VW[i][1])
            else:
                dp[i+1][j] = dp[i][j]

    print((dp[N][W]))


if __name__ == '__main__':
    main()
# Original solution
N, W = list(map(int, input().split()))
dp = [0]*(W+1)
 
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(W, w-1, -1):
        x = dp[j-w] + v
        if x > dp[j]:
            dp[j] = x
 
print(dp[-1])

# Optimized solution
def main():

    N, W = list(map(int, input().split()))
    dp = [0]*(W+1)
 
    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print(dp[-1])

main()
# Original solution
def main():
    n, m = list(map(int, input().split()))
    w = [0] * n
    v = [0] * n
    for i in range(n):
        wt, vt = list(map(int, input().split()))
        w[i] = wt
        v[i] = vt
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, -1, -1):
            l[j] = max(v[i] + l[j-w[i]], l[j]) if j - w[i] >= 0 else l[j]
    print((l[-1]))
main()


# Optimized solution
def main():
    n, m = list(map(int, input().split()))
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, w[i] - 1, -1):
            x = v[i] + l[j-w[i]]
            if x > l[j]:
                l[j] = x
    print((l[-1]))
main()
# Original solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    # dp[i][w]
    #   i番目の品物までで w を超えないように選んだ最大価値
    dp = { 0: 0 }   # { <sum weight>: <sum value> }
    for i in range(1, n + 1):
        dp_ = {}
        wi, vi = list(map(int, input().rstrip().split()))
        for w, v in list(dp.items()):
            w_ = w + wi
            v_ = v + vi
            if w_ <= wlimit and (w_ not in dp or dp[w_] < v_):
                dp_[w_] = v_
        dp.update(dp_)
    return(max(dp.values()))

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))


# Optimized solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = list(map(int, input().rstrip().split()))
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))
# Original solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [0] * (wlimit + 1)
    wv = [list(map(int, input().rstrip().split())) for _ in range(n)]
    for wi, vi in wv:
        dp_ = list(dp)
        for w in range(wlimit + 1):
            v_ = dp[w] if w - wi < 0 else dp[w - wi] + vi
            dp_[w] = max(dp[w], v_)
        dp = dp_
    return(dp[-1])

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))


# Optimized solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = list(map(int, input().rstrip().split()))
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))
# Original solution
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, wv, W):
    dp = [0] * (W + 1)
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = list(map(int, input().split())) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [[int(x) for x in input().split()] for _ in range(n)]

print((f(n, wv, w)))


# Optimized solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = list(map(int, input().rstrip().split()))
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))
# Original solution
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [-1] * (W + 1)
    dp[0] = 0
    for i in range(n):
        wi, vi = list(map(int, input().split()))
        dp_ = list(dp)
        for w in range(W + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= W and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = list(map(int, input().rstrip().split())) # 1 <= n <= 100, 1 <= w <= 10^5

print((f(n, w)))


# Optimized solution
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = list(map(int, input().split()))
        for w in range(W, wi - 1, -1):
            v_ = dp[w - wi] + vi
            if dp[w] < v_:
                dp[w] = v_
    return(dp[-1])

n, w = list(map(int, input().split())) # 1 <= n <= 100, 1 <= w <= 10^5
print((f(n, w)))