CodeEff/ECCO huggingface dataset:
# Original solution
N,W=list(map(int,input().split()))

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    

    for i in range(0, N):
        weights[i],profits[i] = list(map(int,input().split()))
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    for i in range(0, N):
        weights[i],profits[i] = list(map(int,input().split()))
    

    for i in range(0, N):
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()
# Original solution
def main():
    N, W = list(map(int, input().split()))
    wv = [list(map(int, input().split())) for _ in range(N)]
    wl, vl = list(zip(*wv))

    srs = {
        (w, -1): 0 for w in range(W+1)
    }

    def dp(w, i):
        if w - wl[i] < 0:
            return srs[(w, i-1)]
        return max(
            srs[(w - wl[i], i-1)] + vl[i],
            srs[(w, i-1)]
        )
    
    for w in range(W+1):
        for i in range(N):
            srs[(w, i)] = dp(w, i)
    
    print((srs[W, N-1]))


main()


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

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

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

for i, (w, v) in enumerate(wvs):
    i += 1
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j - w] + v, dp[i-1][j])

print((dp[N][W]))
# Original solution
n, W = list(map(int, input().split()))
w, v = [], []

for i in range(n):
    temp1, temp2 = list(map(int, input().split()))
    w.append(temp1)
    v.append(temp2)

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0
    if total > W:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]


print((solve(0, 0)))

# Optimized solution
n, W = list(map(int, input().split()))
w, v = [], []

for i in range(n):
    temp1, temp2 = list(map(int, input().split()))
    w.append(temp1)
    v.append(temp2)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in reversed(list(range(n))):
    for j in reversed(list(range(W))):
        weight, val = w[i], v[i]

        if j + weight <= W:
            chose = dp[i+1][j + weight] + val
            unchose = dp[i+1][j]
            dp[i][j] = max(chose, unchose)
        else:
            dp[i][j] = dp[i+1][j]

#print(dp)
#print(dp[n][W])
print((dp[0][0]))
# Original solution
N, W = list(map(int, input().split()))
w, v = [], []

for i in range(N):
    t1, t2 = list(map(int, input().split()))
    w.append(t1)
    v.append(t2)

def solve(idx, weight, val):
    if weight > W:
        return -1
    if idx == N:
        return val

    # select
    v1 = solve(idx + 1, weight + w[idx], val + v[idx])

    # not select
    v2 = solve(idx + 1, weight, val)

    return max(v1, v2)

print((solve(0, 0, 0)))

# Optimized solution
import sys
sys.setrecursionlimit(10**6)

N, W = list(map(int, input().split()))
w, v = [], []
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(N):
    t1, t2 = list(map(int, input().split()))
    w.append(t1)
    v.append(t2)

for idx in range(1, N+1):
    for weight in range(W+1):
        if weight - w[idx - 1] < 0:
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        # Select
        # v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        # Not Select
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)

# for i in range(N+1):
#     print(dp[i])
print((dp[N][W]))
# Original solution
N, W =  list(map(int, input().split()))
w_list = []
v_list = []
dp = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    w_list.append(w)
    v_list.append(v)
    dp.append({})

dp.append({})

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


for i in range(N):
    for j in range(W + 1):
        sum_w = j
        if sum_w - w_list[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w_list[i]] + v_list[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

print((max(max(x.values()) for x in dp)))


# 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 - w, -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print((max(dp)))
# Original solution
def main():
    N, W =  list(map(int, input().split()))

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = list(map(int, input().split()))
        for i in range(W - w, -1, -1):
            pre_v = dp[i]
            if pre_v == -1: continue
            dp[i + w] = max(dp[i + w], pre_v + v)

    print((max(dp)))

main()


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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = list(map(int, input().split()))
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print((max(dp)))

main()
# Original solution
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""
INF = 100000007


def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp[ww] for ww in range(W + 1))


N, W = list(map(int, input().split()))
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)


# Optimized solution
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""

def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp)


N, W = list(map(int, input().split()))
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)
# Original solution
N,W=list(map(int,input().split()))
A=[]
for _ in range(N):
    B=list(map(int,input().split()))
    A.append(B)
dp=[]
for _ in range(N):
    dp.append([0]*(W+1))
for j in range(W+1):
    if j>=A[0][0]:
        dp[0][j]=A[0][1]
for i in range(0,N-1):
    for w in range(W+1):
        if w>=A[i+1][0]:
            dp[i+1][w]=max(dp[i][w-A[i+1][0]]+A[i+1][1],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print((dp[N-1][W]))

# Optimized solution
N,W = list(map(int,input().split()))
v = [0] * (N)
w = [0] * (N)
for i in range(N):
    w_t,v_t = list(map(int,input().split()))
    v[i] = v_t
    w[i] = w_t

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

for j in range(N):
    for k in range(1,W+1):
        if k >= w[j]:
            dp[j+1][k] = max(dp[j][k],dp[j][k-w[j]]+v[j])
        else:
            dp[j+1][k] = dp[j][k]

print((dp[N][W]))
# Original solution
import sys
input = sys.stdin.readline

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])

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

for i in range(N):
    for j in range(W + 1):
        w, v = wv[i]
        if j >= w:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)
        else:
            dp[i + 1][j] = dp[i][j]

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

# Optimized solution
import sys
input = sys.stdin.readline

n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)]

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

for i in range(1, n + 1):
    w, v = wv[i - 1]
    for j in range(W + 1):
        if j - w >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]

print((dp[-1][-1]))
# Original solution
N,W=list(map(int,input().split()))
w=[]
v=[]
for i in range(N):
    ww,vv=list(map(int,input().split()))
    w.append(ww)
    v.append(vv)

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

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

# Optimized solution
N,W=list(map(int,input().split()))
w=[]
v=[]
for i in range(N):
    ww,vv=list(map(int,input().split()))
    w.append(ww)
    v.append(vv)

dp=[[0 for i in range(W+1)] for j in range(N+1)]

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

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

for i,[W,V] in enumerate(v[1:],1):
    for j in range(w):
        dp[i][w-1-j] = dp[i-1][w-1-j]
        if w-1-j + W <= w:
            dp[i][w-1-j+W] = max(dp[i][w-1-j]+V, dp[i][w-1-j+W])

ans = 0
for i in range(n+1):
    ans = max(ans, max(dp[i]))
print(ans)

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

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

for i,[W,V] in enumerate(v):
    for j in range(w):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + W <= w:
            dp[i+1][j+W] = max(dp[i][j]+V, dp[i+1][j+W])

ans = 0
for i in range(1,n+1):
    ans = max(ans, max(dp[i]))
print(ans)
# Original solution
def chmax(a, b):
	if a < b:
		return b
	return a

def main():
	N, W = list(map(int, input().split()))
	WV = [list(map(int, input().split())) for _ in range(N)]

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			dp[sumw] = chmax(dp[sumw], dp[sumw - w] + v)
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print((main()))


# Optimized solution
def main():
	N, W = list(map(int, input().split()))
	WV = [list(map(int, input().split())) for _ in range(N)]

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			t = dp[sumw - w] + v
			if dp[sumw] < t:
				dp[sumw] = t
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print((main()))
# Original solution
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(eval(input())) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return list(map(int, input().split())) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N,W = imn()
wv = [iln() for _ in range(N)]

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

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

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

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


# Optimized solution
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(eval(input())) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return list(map(int, input().split())) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N,W = imn()
wv = [iln() for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        if sum_w - wv[i][0] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print((dp[N][W]))
# Original solution
n, w = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for _ in range(n)]

# i番目以降の品物で、容量がjのときの価値の最大値


def value(i, j):
    # もう品物がない
    if i == n:
        ret = 0
    # 品物が入らない
    elif j < wv[i][0]:
        ret = value(i+1, j)
    # 品物を入れない場合と入れる場合
    else:
        ret = max(value(i+1, j), value(i+1, j-wv[i][0]) + wv[i][1])
    return ret


print((value(0, w)))


# Optimized solution
n, w = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for _ in range(n)]

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

for i in range(1, n+1):
    wi, vi = wv[i-1]
    for j in range(1, w+1):
        if j < wi:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)
print((dp[-1][-1]))
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = [LI() for _ in range(n)]
    r = [0] * (w+1)
    for a,b in aa:
        for i in range(w-a,-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())


# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    r = [0] * (w+1)
    mx = 0
    for a,b in aa:
        mx += a
        for i in range(min(mx, w-a),-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())
# Original solution
N,W = 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()))
dp = [[int(0) for i in range(W+1)] for i in range(N)]
ans = int(0)
dp[0][0] = 0


for i in range(0,N):
    for j in range(W+1):
        if j==0:
            dp[i][j] = 0
        elif w[i]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i - 1][j - w[i]] + v[i]

ans = max(max(dp))

print(ans)

# Optimized solution

N, W = list(map(int, input().split()))
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = list(map(int, input().split()))

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print((dp[N][W]))
# Original solution
N, W = list(map(int, input().split()))

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


# Optimized solution
def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = list(map(int, input().split()))
print((nap(n, cap)))
# Original solution
N, W = list(map(int, input().split()))

dp = [0]  * (W + 1)
items = []
for i in range(N):
  w, v = list(map(int, input().split()))
  items.append((w, v))

for w, v in items:  
  for wk in range(W, w - 1, -1):
    tv = dp[wk - w] + v
    if tv > dp[wk]:
      dp[wk] = tv
res = max(dp)
print(res)


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

  dp = [0]  * (W + 1)
  items = []
  for i in range(N):
    w, v = list(map(int, input().split()))
    items.append((w, v))

  for w, v in items:  
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
  res = max(dp)
  print(res)

if __name__ == "__main__":
  solve()
# Original solution
n,w=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print((res[w]))

# Optimized solution
import sys
input=sys.stdin.readline
n,w=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print((res[w]))
# Original solution
def solve():
    N, W = list(map(int, input().split()))
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = list(map(int, input().split()))
        w.append(tmpw)
        v.append(tmpv)
    
    dp = [[0] * (W+1) for i 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[-1][-1]))


if __name__ == '__main__':
    solve()


# Optimized solution
def solve():
    N, W = list(map(int, input().split()))
    weight = []
    value = []
    for i in range(N):
        tmpw, tmpv = list(map(int, input().split()))
        weight.append(tmpw)
        value.append(tmpv)
    
    dp = [[0] * (W+1) for i in range(N+1)]
    for i in range(N):
        for w_i in range(W+1):
            if w_i - weight[i] >= 0:
                dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i - weight[i]] + value[i])
            
            dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i])

    print((dp[N][W]))
if __name__ == '__main__':
    solve()
# Original solution
def solve():
    N, W = list(map(int, input().split()))
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = list(map(int, input().split()))
        w.append(tmpw)
        v.append(tmpv)

    dp = [[0 for i in range(W+1)] for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    
    for j in range(W+1):
        dp[0][j] = 0

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

if __name__ == '__main__':
    solve()

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

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

if __name__ == '__main__':
    solve()
# Original solution
import sys
input = sys.stdin.readline

def main():
    N,W = list(map(int,input().split()))
    dp = [0 for _ in range(W+1)]
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(W-nm+1)[::-1]:
            a = nm
            if dp[j+a] < dp[j] + nv:
                dp[j+a] = dp[j] + nv
    print((max(dp)))

if __name__ == "__main__":
    main()

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N,W = list(map(int,input().split()))
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print((max(dp)))

if __name__ == "__main__":
    main()