CodeEff/ECCO huggingface dataset:
# Original solution
N, W = list(map(int, input().split()))
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

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

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

# Optimized solution
n,W=list(map(int,input().split()))
w=[]
val=[]
for i in range(n):
    p=list(map(int,input().split()))
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print((dp[-1]))
# Original solution
N, W = list(map(int, input().split()))
items = [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 - items[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j - items[i][0]] + items[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print((dp[N][W]))


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

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

for i in range(N):
    for w in range(W + 1):
        if w - items[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w], dp[i][w - items[i][0]] + items[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print((dp[N][W]))
# Original solution
cache={}
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif (n,W) in cache:
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      cache[(n,W)]=dp(n-1,W,w,p)
    return cache[(n,W)]
n,W=list(map(int,input().split()))
weight,profit=[],[]
for _ in range(n):
  w,p=list(map(int,input().split()))
  weight.append(w)
  profit.append(p)
print((dp(n,W,weight,profit)))

# Optimized solution
n,W=list(map(int,input().split()))
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif t[n][W]!=-1:
    return t[n][W]
  else:
    if w[n-1]<=W:
      t[n][W]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      t[n][W]=dp(n-1,W,w,p)
    return t[n][W]

weight,profit=[],[]
for _ in range(n):
  w,p=list(map(int,input().split()))
  weight.append(w)
  profit.append(p)
print((dp(n,W,weight,profit)))
# Original solution
# what is dp relation 
# dp[n][w]=max(dp[n-1][w-wt[n]]+p[n],dp[n-1][w])

n,W=list(map(int,input().split()))
wt,p=[],[]
for _ in range(n):
    a,b=list(map(int,input().split()))
    wt.append(a)
    p.append(b)
dp=[[0 for i in range(W+1)]for j in range(n+1)]
for x in range(1,n+1):
    for y in range(1,W+1):
        if wt[x-1]<=y:
            dp[x][y]=max(dp[x-1][y-wt[x-1]]+p[x-1],dp[x-1][y])
        else:
            dp[x][y]=dp[x-1][y]
print((dp[-1][-1]))

# Optimized solution
n,W=list(map(int,input().split()))
wt,p=[],[]
for _ in range(n):
    a,b=list(map(int,input().split()))
    wt.append(a)
    p.append(b)
dp=[0 for i in range(W+1)]
for x in range(1,n+1):
  
  for y in range(W,0,-1):
    if wt[x-1]<=y:
        
      dp[y]=max(dp[y-wt[x-1]]+p[x-1],dp[y])
    else:

      dp[y]=dp[y]
print((dp[-1]))
# 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):
    weight,value = list(map(int,input().split()))
    for j in range(w+1):
        if j >= weight:
            dp[i+1][j] = max(dp[i][j-weight]+value,dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

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(N):
  w,v=list(map(int,input().split()))
  for j in range(W+1):
    if j>=w:
      dp[i+1][j]=max(dp[i][j-w]+v,dp[i][j])
    else:
      dp[i+1][j]=dp[i][j]
print((dp[N][W]))
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def make_v(*args,e=0):
    from copy import deepcopy
    A=e
    for i in args[::-1]: A=[deepcopy(A) for _ in range(i)]
    return A
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=list(map(int,input().split()))
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=list(map(int,input().split()))
    dp=make_v(n+1,w+1)
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print((dp[n][w]))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=list(map(int,input().split()))
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=list(map(int,input().split()))
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print((dp[n][w]))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=list(map(int,input().split()))
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[-INF]*(W+1)
    dp[0]=0
    for w,v in WV:
        for x in range(W,-1,-1):
            if(x+w<=W):
                dp[x+w]=max(dp[x+w],dp[x]+v)

    print((max(dp)))
resolve()

# Optimized solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = list(map(int, input().split()))
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for w0 in range(W, -1, -1):
            if dp[w0] == INF:
                continue
            if w + w0 <= W:
                dp[w + w0] = max(dp[w + w0], dp[w0] + v)
    print((max(dp)))
resolve()
# Original solution
import sys
import pdb
input = sys.stdin.readline

N, W = list(map(int, input().split()))
ws = []
vs = []
for _ in range(N):
  w, v = list(map(int, input().split()))
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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


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

N, W = list(map(int, input().split()))
ws = []
vs = []
for _ in range(N):
  w, v = list(map(int, input().split()))
  ws.append(w)
  vs.append(v)

# Value[i番目までの品番][重さj以下]
Value = [[0 for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

print((Value[N-1][W]))
# Original solution
n,w = list(map(int,input().strip().split()))

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

for i in range(n):
  for sum_w in range(w+1):
    if sum_w >= a[i][0]:
      dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-a[i][0]]+a[i][1])
    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().strip().split()))

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

for i in range(n):
  for sum_w in range(w+1):
    if sum_w >= a[i][0]:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-a[i][0]]+a[i][1])
    dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w])
print((dp[n][w]))
# Original solution

def knapsack(n,c,w,v):
  if n == 0 or c == 0:
    return n
  if w[n] > c:
    return knapsack(n-1,c,w,v)
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v)
    opt2 = knapsack(n-1,c,w,v)
    return max(opt1,opt2)


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

w = [-1]; v = [-1]

for _ in range(n):
  wi , vi= list(map(int,input().split()))
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v)
print(result)        
        
        

# Optimized solution
n ,c = list(map(int,input().split()))
wt =[]; val=[]

for _ in range(n):
  wi , vi = list(map(int,input().split()))
  wt.append(wi)
  val.append(vi)
  
# dp [n][c+1] = 0 
dp = [[0 for i in range(c+1)]for j in range(n)]

for w in range(c+1):
  wi = wt[0]
  if wi<=w:
    dp[0][w]=val[0]
  else:
    dp[0][0]=0

for i in range(1,n):
  wi = wt[i];vi = val[i]
  for w in range(1,c+1):
    if wi<=w:
      dp[i][w] = max(vi+dp[i-1][w-wi] , dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

print((dp[n-1][c]))
# Original solution
from sys import stdin,stdout


def knapsack(i,w):
    if dp[i][w]!=-1:
        return dp[i][w]
    else:
        if w-wi[i]>=0:
            dp[i][w] = max(knapsack(i-1,w-wi[i])+v[i],knapsack(i-1,w))
        else:
            dp[i][w] = knapsack(i-1,w)
        return dp[i][w]
n,w= list(map(int,input().split()))
wi=[0]
v=[0]
for i in range(n):
    x,y= list(map(int,stdin.readline().split()))

    wi.append(x)
    v.append(y)
dp = [[-1 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
    dp[0][i]=0
for j in range(n+1):
    dp[j][0]=0
stdout.write(str(knapsack(n,w)) + "\n")
#print(dp)

# Optimized solution
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+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i+w],dp[i]+v)
print((max(dp)))
# Original solution
num, capacity = list(map(int, input().split()))
dp = [0]*(capacity+1)

for _ in range(num):
    weight, value = list(map(int, input().split()))
    for w in range(capacity,weight - 1,-1):
        tmp = dp[w - weight] + value
        if dp[w] < tmp:
          dp[w] = tmp
print((dp[capacity]))

# Optimized solution
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = list(map(int, input().split()))
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = list(map(int, input().split()))
print((calc(num,capacity)))
# Original solution
n, weightMax = list(map(int, input().split()))
itemList = [[0 for _ in range(weightMax+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in reversed(list(range(weightMax+1))):
        if j-w >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-w] + v])
        else:
            itemList[i+1][j] = itemList[i][j]
print((max(itemList[n])))


# Optimized solution
n, max_weight = list(map(int, input().split()))
dp = [[0 for _ in range(max_weight+1)] for _ in range(n+1)]

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

DP = {0: 0}
for i in range(N):
    wi, vi = list(map(int, input().split()))
    DP_dst = DP.copy()
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print((max((DP[x] for x in DP))))


# Optimized solution
# TODO:実装
N, W = list(map(int, input().split()))

DP = {0: 0}
for i in range(N):
    wi, vi = list(map(int, input().split()))
    DP_dst = DP.copy()
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print((max((DP[x] for x in DP))))
# Original solution
n,tw = list(map(int, input().split()))
wt = [];    val = []
for i in range(n):
    a,b = list(map(int, input().split()))
    wt.append(a);   val.append(b)
dp = [[0 for i in range(tw+1)] for j in range(n+1)]
for i in range(n):
    for j in range(1,tw+1):
        if j < wt[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], val[i]+dp[i][j-wt[i]])
print((dp[n][tw]))


# Optimized solution
def ks(n, W, arr):
    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(1,W+1):
            if arr[i-1][0] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i-1][0]]+arr[i-1][1])
    return dp[n][W]

if __name__ == "__main__":
    n, W = list(map(int, input().split()))
    arr = []
    for i in range(n):
        w,v = list(map(int, input().split()))
        arr.append([w,v])
    arr.sort(key = lambda x:x[0])
    ans = ks(n,W,arr)
    print(ans)
# Original solution
import sys
input = sys.stdin.readline
n,w=list(map(int,input().split()))
dp=[[0]*(w+1) for _ in range(n)]
l=[0]*n
for i in range(n):
    l[i]=list(map(int,input().split()))
#print(l)
for i in range(w+1):
    if i>=l[0][0]:
        dp[0][i]=l[0][1]
for i in range(w+1):
    for j in range(n-1):
        if i<l[j+1][0]:
            dp[j+1][i]=dp[j][i]
        else:
            dp[j+1][i]=max(dp[j][i-l[j+1][0]]+l[j+1][1],dp[j][i])


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

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


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


# Optimized solution
n, w = list(map(int, input().split()))
goods = [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 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print((dp[n][w]))
# Original solution
def knapsack(sizes, vals, volume):
    n = len(sizes)

    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])
            dp[i][j] = max(dp[i][j], dp[i-1][j])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print((knapsack(sizes, vals, volume)))


# Optimized solution
def knapsack(sizes, vals, volume):
    n = len(sizes)

    dp = [[0] * (volume+1) for _ in range(n)] # j is 0...volume

    for i in range(n):
        for j in range(volume+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j - sizes[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-sizes[i]] + vals[i])
            #dp[i][j] = max(dp[i][j], dp[i-1][j])

    return dp[-1][-1]


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print((knapsack(sizes, vals, volume)))
# Original solution
from collections import Counter
from functools import reduce
import fractions
import pprint
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


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

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

P(max(dp[-1]))


# Optimized solution
N, W = list(map(int,input().split()))
dp = [[0 for i in range(100001)] for i in range(N+1)]

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

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

print((max(dp[-1])))
# Original solution
N, W = list(map(int, input().split(" ")))

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

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


# Optimized solution
N, W = list(map(int, input().split(" ")))
dp =  [[0] * (W+1) for _ in range(N+1)]
 
for i in range(0, N):
	weight, value = list(map(int, input().split(" ")))
	for w in range(1, W+1):
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print((dp[N][W]))
# Original solution
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N, M = list(map(int, input().split()))
W = [0] * (N +2)
V = [0] * (N +2)
for i in range(0, N):
    W[i],V[i] = list(map(int, input().split()))

for i in range(0, N):
    for j in range(1, M+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)])

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[(i,j)])
    print('')
'''

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


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

for i in range(1, N+1):
    W,V = list(map(int,input().split()))
    for j in range(W):
        dp[i][j] = dp[i-1][j]
    for j in range(M-W+1):
        dp[i][j+W] = max(dp[i-1][j+W],dp[i-1][j]+V)

print((max(dp[-1])))
# Original solution
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N, M = list(map(int, input().split()))
W = [0] * (N +2)
V = [0] * (N +2)
for i in range(0, N):
    W[i],V[i] = list(map(int, input().split()))

for i in range(0, N):
    for j in range(0, W[i]+1):
        dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j)])
    for j in range(W[i], M+1):
        dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j-W[i])] + V[i])

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[(i,j)])
    print('')
'''

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


# Optimized solution
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
N, M = list(map(int, input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]

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

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[i][j])
    print('')
'''

print((max(dp[-1])))
# Original solution
def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]
  dp[0] = 0

  for i in range(N + 1):
    i_weight, i_value = weight_values[i - 1]
    for w in range(W, -1, -1):
      if i_weight <= w:
        dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      else:
        dp[w] = dp[w]

  print((dp[W]))

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


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)


# Optimized solution
def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]

  for i in range(N):
    i_weight, i_value = weight_values[i]
    for w in range(W, i_weight - 1, -1):
      # dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      temp = dp[w - i_weight] + i_value
      if temp > dp[w]:
        dp[w] = temp

  print((dp[W]))

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


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)
# 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 _ in range(W+1)] for _ in range(N+1)]

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

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+1)]
for i in range(1, N+1):
    for s in range(1, W+1):
        if w[i-1] <= s:
            dp[i][s] = max(dp[i][s], dp[i-1][s-w[i-1]] + v[i-1])
        dp[i][s] = max(dp[i][s], dp[i-1][s])

print((dp[N][W]))
# 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)]

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

print((max(dp)))

# Optimized solution
def MI(): return list(map(int, input().split()))
import sys
input = sys.stdin.readline
n,w = list(map(int,input().split()))
#wv = [tuple(map(int,input().split())) for i in range(n)]
W=[]
V=[]
for i in range(n):
  a,b=MI()
  W.append(a)
  V.append(b)
dp = [0]*(w+1)
for i in range(n):
    for j in range(w,W[i]-1,-1):
        dp[j] = max(dp[j],dp[j-W[i]]+V[i])
print((max(dp)))