CodeEff/ECCO huggingface dataset:
# 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,-1,-1):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dp[cw]<cv:
			dp[cw]=cv
print((dp[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 j in range(W-w,-1,-1):
		dp[j+w]=max(dp[j+w],dp[j]+v)
print((dp[W]))
# Original solution
n,w=list(map(int,input().split()))
a=[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):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print((dp[-1][-1]))

# Optimized solution
n,W=list(map(int,input().split()))
a=[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):
    weight,value=a[i]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=W:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print((dp[-1][-1]))
# Original solution
N, W = list(map(int, input().split()))
item = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*100100 for _ in range(110)]

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

        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()))
dp = [[0]*100100 for _ in range(110)]

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

        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]*100100 for _ in range(110)]

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

        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()))

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

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

print((dp[N][W]))
# Original solution

import os
import sys
from io import BytesIO, IOBase

def knapsack(wt,price,n,c,dp):
    if n<0 or c==0:
        return 0
    if dp[n][c]!=-1:
        return dp[n][c]
    inc=exc=0
    if c>=wt[n]:
        inc=price[n]+knapsack(wt,price,n-1,c-wt[n],dp)
    exc=0+knapsack(wt,price,n-1,c,dp)
    dp[n][c]=max(inc,exc)
    return max(inc,exc)

def main():
    n,c=list(map(int,input().split()))
    wt=[]
    price=[]
    for _ in range(n):
        w,v=list(map(int,input().split()))
        wt.append(w)
        price.append(v)
    dp=[[-1 for x in range(c+1)] for y in range(n+1)]
    print((knapsack(wt,price,n-1,c,dp)))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

# Optimized solution
def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)
    
    return dp[n][c]
  
n,c=list(map(int,input().split()))
wt=[]
price=[]
for _ in range(n):
    w,v=list(map(int,input().split()))
    wt.append(w)
    price.append(v)
print((knapsackBottomUp(wt,price,c,n)))
# Original solution
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]))

# 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 wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print((dp[w]))


if __name__ == '__main__':
    main()
# Original solution
import sys

input = sys.stdin.readline


def main():
    N, W = list(map(int, input().split()))
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            elif dp_im[j - w] + v > dp_im[j]:
                dp_i[j] = dp_im[j - w] + v
            else:
                dp_i[j] = dp_im[j]

    ans = dp[-1][-1]
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline


def main():
    N, W = list(map(int, input().split()))
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b

    ans = dp[-1][-1]
    print(ans)


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

# Optimized solution
def calc():
  N,W=list(map(int,input().split()))
  dp=[-1]*(W+1)
  dp[0]=0
  for i in range(N):
    w,v=list(map(int,input().split()))
    for j in range(W-w,-1,-1):
      if dp[j]!=-1:
        if dp[j+w]<dp[j]+v:
          dp[j+w]=dp[j]+v
  print((max(dp)))
  
calc()
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  # dp[i+1][j] iまでで最大化
  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])

  return dp[n][W]

# main()
print((main()))


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

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  # dp[i+1][j] iまでで最大化
  for i in range(n):
    for j in range(W+1):
      dp[i+1][j]=max(dp[i+1][j],dp[i][j])
      if j+w[i]<=W:
        dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])
  return dp[n][W]

# main()
print((main()))
# Original solution
import copy
n,w=list(map(int,input().split()))
wv=[list(map(int,input().split())) for _ in range(n)]
dp=([0]*wv[0][0])+[wv[0][1]]*(w+1-wv[0][0])
for i in range(n-1):
    dp_copy=copy.deepcopy(dp)
    for j in range(w+1):
        if j>=wv[i+1][0]:
            dp[j]=max(dp_copy[j],dp_copy[j-wv[i+1][0]]+wv[i+1][1])
print((dp[-1]))

# Optimized solution
n,w=list(map(int,input().split()))
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]
print((dp[-1][-1]))
# Original solution
# D-Knapsack 1
N,W = list(map(int,input().split()))
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[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):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        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])

        #　i番目を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

# for d in dp:
#     print(d)

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

# Optimized solution
# D-Knapsack 1
N,W = list(map(int,input().split()))
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = list(map(int,input().split()))

# dp[i+1][w]:= i番目までの品物の中から重さがwを超えないように選んだときの、価値の総和の最大値
dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        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])

        # i番目を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

# for d in dp:
#     print(d)

print((dp[N][W]))
# Original solution
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, w = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

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

    for i in range(n):
        for j in reversed(list(range(i+1))):
            for k in range(w+1):
#                if (Knap[j][k] > 0 or (j == 0 and k ==0)) and k + A[i][0] <= w:
                point = k + A[i][0]
                if point <= w:
                    Knap[j+1][k + A[i][0]] = max((Knap[j+1][point]), (Knap[j][k] + A[i][1]))

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

resolve()

# Optimized solution
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, w = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

    Knap = [[0] * (w+1) for _ in range(n+1)]
#    Knap = [[0] * (110) for _ in range(10**5+10)]

    for i in range(n):
        for k in range(w+1):
            if k + A[i][0] <= w:
#                point = k + A[i][0]
                Knap[i+1][k+A[i][0]] = max(Knap[i+1][k+A[i][0]], (Knap[i][k] + A[i][1]))

            Knap[i+1][k] = max(Knap[i][k], Knap[i+1][k])

#    knapmax = 0
    # for i in range(n):
    #     knapmax = max(knapmax, max(Knap[i+1]))
    print((Knap[n][w]))
#    print(*Knap, sep="\n")
resolve()
# Original solution
N,W = list(map(int,input().split()))
w = []
v = []
for i in range(N):
  w_,v_ = list(map(int,input().split()))
  w.append(w_)
  v.append(v_)

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

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print((memo(0,W)))

# Optimized solution
import sys
sys.setrecursionlimit(10**9)
N,W = list(map(int,input().split()))
w = []
v = []
for i in range(N):
  w_,v_ = list(map(int,input().split()))
  w.append(w_)
  v.append(v_)

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

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print((memo(0,W)))
# Original solution
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
 
# グローバル変数定義
INF = 10 ** 13
N, W = list(map(int, input().split()))
 
# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]
 
# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]
 
 
def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。
 
    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和
 
    Returns:
        v (int) : 価値の総和の最大値
    """
 
    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0
 
    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])
 
 
def main():
    out = dfs(0, 0)
    print(out)
 
 
if __name__ == "__main__":
    main()

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


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

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

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

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


if __name__ == "__main__":
    main()
# Original solution
n, mw = list(map(int, input().split()))
w, v = [], []
for _ in range(n):
    x, y = list(map(int, input().split()))
    w.append(x)
    v.append(y)
dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(mw+1):
        if w[i-1] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        else:
            dp[i][j] = dp[i-1][j]
print((dp[n][mw]))


# Optimized solution
n, mw = list(map(int, input().split()))
goods = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(mw+1):
        w, v = goods[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][mw]))
# Original solution
N,W=list(map(int,input().split()))
w,v=[],[]
for i in range(N):
  a,b=list(map(int,input().split()))
  w.append(a)
  v.append(b)
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
      if j-w[i]>=0:
          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]*(W+1) for i 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][j-w[i]]+v[i],dp[i+1][j])
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])

print((dp[-1][-1]))
# Original solution
def main():
    N, W = [int(n) for n in input().split()]
    baggages = [[int(n) for n in input().split()] for i in range(N)]

    VALUE, WEIGHT = 1, 0
    dp = [[-1] * (W+1) for n in range(N)]
    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える
    dp[0] = [0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] for weight in range(W+1)]

    for baggage in range(N):
        for max_weight in range(W+1):
            if dp[baggage][max_weight] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][max_weight]
            val2 = dp[baggage-1][max_weight-bag_w]+bag_v if max_weight >= bag_w else 0
            dp[baggage][max_weight] = max(val1, val2)
            
    print((dp[N-1][W]))



if __name__ == "__main__":
    main()

# Optimized solution
N,W = [int(_n) for _n in input().split()]
A = []
for i in range(N):
    w,v = [int(_n) for _n in input().split()]
    A.append((w,v))
dp = [[0]*(W+1) for _ in range(N)]

for w in range(W+1):
    dp[0][w] = 0 if w < A[0][0] else A[0][1]

for i in range(N):
    for w in range(W+1):
        dp[i][w] = dp[i-1][w]
        if w >= A[i][0]:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-A[i][0]] + A[i][1])
print((dp[N-1][W]))
# Original solution
import sys
sys.setrecursionlimit(10 ** 8)

N, W = list(map(int, input().split()))
w = []
v = []
for i in range(N):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)
    
dp = [[-1] *(W + 1) for i in range(N + 1)]
    
def dfs(i, W):
    if dp[i][W] != -1:
        return dp[i][W]
    if i == N:
        ans = 0
    elif w[i] > W:
        ans = dfs(i + 1, W)
    else:
        ans = max(dfs(i + 1, W), dfs(i + 1, W - w[i]) + v[i])
    dp[i][W] = ans
    return ans

print((dfs(0, W)))

# Optimized solution
N, W = list(map(int, input().split()))
w = []
v = []
for i in range(N):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)
    
dp = [[0] *(W + 1) for i 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]))
# Original solution
N, W = list(map(int, input().split()))
w_list = []
v_list = []
for i in range(N):
    w, v = list(map(int, input().split()))
    w_list.append(w)
    v_list.append(v)
dp = [[0 for i in range(W+1)] for i in range(N)]
for i in range(N):
    w = w_list[i]
    v = v_list[i]
    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[N-1][W]))

# Optimized solution
N,W = list(map(int,input().split()))
w_list = []
v_list = []
for _ in range(N):
    w,v = list(map(int,input().split()))
    w_list.append(w)
    v_list.append(v)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
    w = w_list[i-1]
    v = v_list[i-1]
    for j in range(1,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[N][W]))
# Original solution
N,W = list(map(int,input().split()))
w_list = []
v_list = []
for _ in range(N):
    w,v = list(map(int,input().split()))
    w_list.append(w)
    v_list.append(v)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
    w = w_list[i-1]
    v = v_list[i-1]
    for j in range(1,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[N][W]))

# Optimized solution
n,W = list(map(int,input().split()))
dp = [[0]*(W+1) for i in range(n)]
for i in range(n):
    w,v = list(map(int,input().split()))
    if i == 0:
        for j in range(W+1):
            if w <= j:
                dp[0][j] = v
    else:
        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[-1][-1]))
# Original solution
n,w=list(map(int,input().split()))
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print((max(dp[n])))

# Optimized solution
# 貰うDP
n, w = list(map(int, input().split()))
WV = [list(map(int, input().split())) for i in range(n)]
# dp[i][w] 重さwでの最高価値
dp = [[-1] * (w + 1) for i in range(n + 1)]
for j in range(w + 1):
    dp[0][j] = 0
for i in range(n):
    for j in range(w + 1):
        if j - WV[i][0] >= 0 and j - WV[i][0] <= w:
            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((dp[n][w]))
# Original solution
n, m = list(map(int, input().split()))
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W[i]):
        DP[i+1][j] = DP[i][j]
    for j in range(W[i], m+1):
        DP[i+1][j] = max(DP[i][j], DP[i][j-W[i]]+V[i])
print((DP[n][m]))


# Optimized solution
n, m = list(map(int, input().split()))
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(W[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(W[i-1], m+1):
        DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i-1]]+V[i-1])
print((DP[n][m]))