CodeEff/ECCO huggingface dataset:
# Original solution
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    # W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print((dp[-1][-1]))


main()


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


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print((dp[-1][-1]))


main()

# pythonでもpypyでもTLE
# Original solution
N, W = list(map(int, input().split()))
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = list(map(int, input().split())) 
  ws[i] = w
  vs[i] = v
 
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
 
print((max(dp[-1])))

# Optimized solution
n, W = list(map(int, input().split()))
ws = [0]*n
vs = [0]*n

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

Item = namedtuple('Item', 'w v')

N, W = (int(x) for x in input().split())

items = []

for _ in range(N):
  w, v = (int(x) for x in input().split())
  items.append(Item(w, v))

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

for i in range(N):
  for w in range(W + 1):
    if i == 0:
      # 1行目を初期化
      memo[i][w] = items[i].v if items[i].w <= w else 0
      continue
    if w < items[i].w:
      # 入らなければひとつ上の行の値をそのまま使う
      memo[i][w] = memo[i - 1][w]
      continue
    memo[i][w] = max(memo[i - 1][w], memo[i - 1][w - items[i].w] + items[i].v)

print((memo[N - 1][W]))

# Optimized solution
from collections import namedtuple


Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = list(map(int, input().split()))
  items.append(Item(w, v))

memo = [0] * (W + 1)

for item in items:
  for w in range(W, item.w - 1, -1):
    memo[w] = max(memo[w], memo[w - item.w] + item.v)
    
print((memo[W]))
# Original 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]))

# Optimized solution
n, W = list(map(int,input().split()))
items = [[0,0] for _ in range(n+1)]
for i in range(n):
    items[i+1] = list(map(int, input().split()))

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    weight, value = items[i][0], items[i][1]
    for w_limit in range(1,W+1):
        if w_limit - weight >= 0:
            dp[i][w_limit] = max(dp[i-1][w_limit], dp[i-1][w_limit-weight] + value)
        else:
            dp[i][w_limit] = dp[i-1][w_limit]
print((dp[n][W]))
# Original solution
n, w = list(map(int,input().split()))
wv = [list(map(int,input().split())) for _ in range(n)]

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

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

print((max(dp[-1])))

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

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

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

print((max(dp[-1])))
# Original solution
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[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print((dp[n][w]))

# Optimized solution
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[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[None for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print((max(i for i in dp[n] if i is not None)))
# Original solution
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[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[None for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print((max(i for i in dp[n] if i is not None)))


# Optimized solution
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[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(w+1):
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        if(j - weight[i-1] >= 0):
            dp[i][j] = max(dp[i-1][j-weight[i-1]]+value[i-1],dp[i][j])
            
print((dp[n][w]))
# Original solution
n,wgt=list(map(int,input().split()))
a=[]
v=[]
for i in range(n):
    x,y=list(map(int,input().split()))
    a.append(x)
    v.append(y)

d={}

def dp(wgt,n): 
    if n==0 or wgt==0: 
        return 0
    if(a[n-1]>wgt):
        if((wgt,n-1) in d):
            return d[(wgt,n-1)] 
        return dp(wgt,n-1) 
    else:
        d1=0
        if (wgt,n-1) in d:
            d1=d[(wgt,n-1)]
        else:
            d1=dp(wgt,n-1)
        d2=0
        if (wgt-a[n-1],n-1) in d:
            d2=d[(wgt-a[n-1],n-1)]
        else:
            d2=dp(wgt-a[n-1],n-1)
        return max(v[n-1]+d2,d1)
print((dp(wgt,n)))

# Optimized solution
n,wgt=list(map(int,input().split()))
a=[]
v=[]
for i in range(n):
    x,y=list(map(int,input().split()))
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

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

print((dp[n][wgt]))
# Original solution
N, W = list(map(int, input().split()))
w_v = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1 for _ in range(W+1)] for _ in range(N)]

# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値を返す
def f(i, j):
    # 終了条件
    if i == N:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    w, v = w_v[i]

    # これ以上入らないとき
    if j - w < 0:
        dp[i][j] = f(i+1, j)

    # まだ入るときは両方試す
    else:
        dp[i][j] = max(f(i+1, j), f(i+1, j-w)+v)
    return dp[i][j]

print((f(0, W)))


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


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

print((max(dp[N])))
# Original solution
N, W = list(map(int, input().split()))
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

print((max(dp[N])))





# Optimized solution
n, W = list(map(int, input().split()))
data = []
for _ in range(n):
    w, v = list(map(int, input().split()))
    data.append((w, v))

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

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

print((dp[-1][W]))
# Original solution
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(eval(input()))


def tinput():
    return input().split()


def rinput():
    return list(map(int, tinput()))


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, w = rinput()
    w_v = []
    for i in range(n):
        w_v.append(rlinput())
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    # print(w_v)
    for item in range(1, n+1):
        for weight in range(1, w+1):
            if weight >= w_v[item-1][0]:
                dp[item][weight] = max(dp[item-1][weight-w_v[item-1][0]]+w_v[item-1][1],dp[item-1][weight])
            else:
                dp[item][weight] =dp[item-1][weight]
    print((dp[n][w]))


# Optimized solution




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

    # dp[i][w] is the maximum value got with first i items stored in w weight of knapsack
    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=weight[i]:
                dp[i][w] = max(dp[i-1][w],dp[i-1][w-weight[i]]+value[i])
            else:
                dp[i][w] = dp[i-1][w]
    print((dp[N][W]))





if __name__ == "__main__":
    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=[[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]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print((dp[N][W]))

# Optimized 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=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print((dp[W]))
# Original solution
N,W = list(map(int,input().split()))
dp=[[0]*(W+100) for _ in range(N+10)]
for i in range(N):
    w,v= list(map(int,input().split()))
    for j in range(W+1):
        if j-w>=0:
            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
N,W = list(map(int,input().split()))
p=[[0]*(W+100) for _ in range(N+10)]
for i in range(N):
    w,v= list(map(int,input().split()))
    for j in range(W+1):
        if j>=w:
            p[i+1][j] = max(p[i][j],p[i][j-w]+v)
        else:
            p[i+1][j]=p[i][j]
print((p[N][W]))
# Original solution
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

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

dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]

for i in range(N):
    for w_sum in range(W+1):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

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


# Optimized solution
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, W = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]

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

for i in range(N):
    for w_sum in range(W+1):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum+items[i][0] <= W:
            dp[i+1][w_sum+items[i][0]] = max(dp[i+1][w_sum+items[i][0]],
                                             dp[i][w_sum]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

ans = 0
for w in range(W+1):
    ans = max(ans, dp[N][w])
print(ans)
# Original solution
N, W, *A = list(map(int, open(0).read().split()))
A = list(zip(*[iter(A)]*2))

# dp[i][j] iまでの品物からいくつか選んで残り容量がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(A):
    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], dp[i][j-w]+v)

print((max(dp[N])))

# Optimized solution
N, W, *A = list(map(int, open(0).read().split()))
A = list(zip(*[iter(A)]*2))

# dp[i][j] iまでの品物からいくつか選んで重さの総和がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(A):
    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], dp[i][j-w]+v)

print((max(dp[N])))
# Original solution
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
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 - 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]))


# Optimized solution
def main():
    N, W = list(map(int, input().split()))
    wv = [list(map(int, input().split())) for _ in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    vdp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for weight in range(W+1):
            # 品物iを（選べるなら）選ぶ
            if weight >= w[i]: vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight])
            # 品物iを選ばない
            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])
    print((vdp[N][W]))

if __name__ == '__main__':
    main()
# Original solution
def main():
    n,w=list(map(int,input().split()))
    items=[]
    dp=[0 for i in range(w+1)]
    for i in range(n):
        wi,vi=list(map(int,input().split()))
        for j in range(w-wi,-1,-1):
            dp[j+wi]=max(dp[j+wi],dp[j]+vi)
    print((max(dp)))
if __name__=='__main__':
    main()


# Optimized solution
n,w=list(map(int,input().split()))
items=[]
dp=[0 for i in range(w+1)]
for i in range(n):
    wi,vi=list(map(int,input().split()))
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print((max(dp)))
# Original solution
N,W = [int(s) for s in input().split()]
dp = [[0]*(W+1) for _ in range(N+1)]

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

# Optimized solution
N,W = [int(s) for s in input().split()]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_w in range(W+1):
        if sum_w - w >= 0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-w] + v)
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print((dp[N][W]))
# Original solution
N,W = list(map(int,input().split()))
# wv_list = [tuple(map(int,input().split())) for _ in range(N)]
w_list = []
v_list = []
for i in range(N):
    w,v = list(map(int,input().split()))
    w_list.append(w)
    v_list.append(v)

memo = [[None  for _ in range(W+1)] for _ in range(N+1)]

def rec(check_item,residual_w):
    if memo[check_item][residual_w]:
        return memo[check_item][residual_w]    
    if check_item == N:
        res = 0
    elif residual_w < w_list[check_item]:
        res = rec(check_item+1, residual_w)
    else:
#         print(check_item,residual_w)
        res = max(rec(check_item+1,residual_w),
                  rec(check_item+1,residual_w-w_list[check_item])+v_list[check_item])
    memo[check_item][residual_w] = res
    
    return res

print((rec(0,W)))

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

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

for weight,value in wv_list:
    for w in range(W+1)[::-1]:
        if w  >= weight:
            memo[w] = max(memo[w], memo[w-weight]+value)
            
print((memo[W]))
# Original solution
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

#pprint(dp_table)



# Optimized solution
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)
# Original solution
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)


# Optimized solution
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i-1][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            #i番目の品物を選ばない場合
            dp_table[i][sum_w] = dp_table[i-1][sum_w]


result = dp_table[n][w]
print(result)
# Original solution
n,w = list(map(int,input().split()))
inf = float("inf")
dp = [[-inf]*(w+1) for _ in range(n+1)]
for j in range(w+1):
    dp[0][j] = 0
for i in range(n):
    s,t = list(map(int,input().split()))
    for l in range(w+1):
        if l-s >=0:
            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+t)
        else:
            dp[i+1][l] = dp[i][l]
print((dp[-1][w]))        

# Optimized solution
n,w = list(map(int,input().split()))
ls = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for p in range(w+1):
        if p >= ls[i][0]:
            dp[i+1][p] = max(dp[i][p],dp[i][p-ls[i][0]]+ls[i][1])
        else:
            dp[i+1][p] = dp[i][p]
print((dp[n][w]))