CodeEff/ECCO huggingface dataset:
# Original solution
from bisect import bisect_left
def main():
    n, w = list(map(int, input().split()))
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(list(range(item[i][0], min(w+1, x+item[i][0]+1)))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    print((max(dp)))

if __name__ == "__main__":
    main()


# Optimized solution
from bisect import bisect_left
def main():
    n, w = list(map(int, input().split()))
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(list(range(p, min(w+1, x+p+1)))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print((max(dp)))

if __name__ == "__main__":
    main()
# Original solution
n, w = list(map(int, input().split()))
things = []
things.append([0,0])
things += [list(map(int, input().split())) for _ in range(n)]

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

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

do_dp()
print((dp[n][w]))


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

dp = [0]*(w+1)

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

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

for i in range(1, N + 1):
    w, v = list(map(int, input().split()))
    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((max(dp[N])))

# Optimized 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(1, N + 1):
    w, v = list(map(int, input().split()))
    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
# D - Knapsack 1
from collections import defaultdict


def main():
    N, W, *WV = list(map(int, open(0).read().split()))
    dp = defaultdict(int)
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_w, cur_v in tuple(dp.items()):
            if w + cur_w <= W:
                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)
    print((max(dp.values())))


if __name__ == "__main__":
    main()


# Optimized solution
# D - Knapsack 1
def solve_knapsack(weight_limit: int, weights: list, values: list) -> int:
    dp = [0] * (weight_limit + 1)  # dp[i] := optimum value at weight i
    for w, v in zip(weights, values):
        for cur_w in range(weight_limit, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W, *WV = list(map(int, open(0).read().split()))
    print((solve_knapsack(W, WV[::2], WV[1::2])))


if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    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,-1,-1):# 後ろから更新しないとダメ
            if j - w >= 0:
                dp[j] = max(dp[j], dp[j-w]+v)
    print((dp[W]))    

if __name__ == "__main__":
    main()


# Optimized solution
def main():
    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,-1,-1):# 後ろから更新しないとダメ
            if j - w >= 0:
                dp[j] = max(dp[j], dp[j-w]+v)
    print((dp[W]))    

if __name__ == "__main__":
    main()
# Original solution
from sys import stdin
from collections import defaultdict
n, w = [int(i) for i in stdin.readline().split(' ')]
weights = []
values = []
for i in range(0, n):
    cur = [int(i) for i in stdin.readline().split(' ')]
    weights.append(cur[0])
    values.append(cur[1])

dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 0+0
for minInd in range(0, n):
    for allowed in range(0, w):
        dp[minInd+1][allowed] = max(dp[minInd+1][allowed], dp[minInd][allowed])
        if allowed+weights[minInd] <= w:
            dp[minInd+1][allowed+weights[minInd]] = max(dp[minInd+1][allowed+weights[minInd]], dp[minInd][allowed]+values[minInd])

print((max(dp[n].values())))


# Optimized solution
def woo(n, w):
	res = [0 for i in range(0, w+1)]

	for i in range(0, n):
		ww, vv = list(map(int, input().split()))
		for j in range(w, ww-1, -1):
			wtotal = j + ww
			vtotal = res[j-ww] + vv
			if vtotal > res[j]:
				res[j] = vtotal

	return res

if __name__ == '__main__':
	n, w = list(map(int, input().split()))
	r = woo(n, w)
	print((max(r)))
# Original solution
def woo(n, w):
	res = [0 for i in range(0, w+1)]

	for i in range(0, n):
		ww, vv = list(map(int, input().split()))
		for j in range(w, ww-1, -1):
			wtotal = j + ww
			vtotal = res[j-ww] + vv
			if vtotal > res[j]:
				res[j] = vtotal

	return res

if __name__ == '__main__':
	n, w = list(map(int, input().split()))
	r = woo(n, w)
	print((max(r)))

# Optimized solution
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print((t[w][n]))
    return 0

if __name__ == "__main__":
    main()
# Original solution
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print((t[w][n]))
    return 0

if __name__ == "__main__":
    main()

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

w = []
v = []

for x in range(n):
    peso,valor = list(map(int,input().split()))
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

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


resposta = 0

for x in dp:
    resposta = max(x,resposta)

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

# Optimized solution
def main():
    n, w = list(map(int, input().split()))
    dp = [-1] * (w + 1)
    dp[w] = 0
    for i in range(n):
        input_w, input_v = list(map(int, input().split()))
        for i in range(input_w, w + 1):
            if dp[i] == -1:
                continue
            if dp[i - input_w] < dp[i] + input_v:
                dp[i - input_w] = dp[i] + input_v
    print((max(dp)))

main()
# Original solution
import sys

input = sys.stdin.readline


def main():
    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 j in range(N)]

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

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

if __name__ == '__main__':
    main()


# Optimized solution
import sys

input = sys.stdin.readline


def main():
    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 j in range(N + 1)]

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

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

if __name__ == '__main__':
    main()
# Original solution
def resolve():
    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(1, n + 1):
        for j in reversed(list(range(w + 1))):
            # もしi番目の品物が入るのであれば
            if goods[i - 1][0] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    print((dp[n][w]))
    
resolve()

# Optimized solution
def resolve():
    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(1, n + 1):
        for j in reversed(list(range(w + 1))):
            tmp = dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1] if j >= goods[i - 1][0] else 0
            dp[i][j] = max(dp[i - 1][j], tmp)

    print((dp[n][w]))

resolve()
# Original solution
N, W = list(map(int, input().split()))
W += 1
A = [[0] * W for _ in range(N)]
wi, vi = list(map(int, input().split()))

for w in range(W):
    A[0][w] = 0 if w < wi else vi

for i in range(1, N):
    wi, vi = list(map(int, input().split()))
    for w in range(W):
        A[i][w] = max([
            A[i-1][w_] + vi for w_ in range(w - wi + 1)
        ] + [A[i-1][w]])

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

# Optimized solution
N, W = list(map(int, input().split()))
W += 1
A = [0] * W
wi, vi = list(map(int, input().split()))
A[wi] = vi

for _ in range(N-1):
    wi, vi = list(map(int, input().split()))
    tmp = [0] * W

    for w in range(W):
        if w-wi < 0:
            tmp[w] = A[w]
        else:
            tmp[w] = max(A[w-wi] + vi, A[w])

    A = tmp

print((max(A)))
# Original solution
def rec(depth, w, v):
    if w > maxW:
        return
    WV[depth][w] = max(v, WV[depth][w])
    if depth+1 >= N:
        return
    rec(depth+1, w+W[depth+1], v+V[depth+1])
    rec(depth+1, w, v)


N, maxW = list(map(int, input().split()))
WV = [[-1 for i in range(maxW+1)] for j in range(N)]
W = [0 for i in range(N)]
V = [0 for i in range(N)]
for i in range(N):
    W[i], V[i] = list(map(int, input().split()))
rec(0, 0, 0)
rec(0, W[0], V[0])
print((max(WV[-1])))


# Optimized solution
N, maxW = list(map(int, input().split()))
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = list(map(int, input().split()))

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print((max(WV[-1])))
# Original solution
def main():
  from collections import deque
  n,w=list(map(int,input().split()))
  item=deque([list(map(int,input().split())) for _ in range(n)])
  DP=[[0]*(w+1) for _ in range(n+1)]
  for i in range(1,n+1):
    itemNow=item.popleft()
    weight=itemNow[0]
    value=itemNow[1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print((DP[n][w]))
      
if __name__=="__main__":
  main()

# Optimized solution
def main():
  import sys
  num,capacity=list(map(int,input().split()))
  items=tuple([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  for item in items:
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print((max(DP)))
      
if __name__=="__main__":
  main()
# Original solution
def main():
  import sys
  sys.setrecursionlimit(10**7)
  N,W=list(map(int,sys.stdin.readline().split()))

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

  WL=[0]* N
  VL=[0]*N

  for i in range(N):
      w,v=list(map(int,sys.stdin.readline().split()))
      WL[i]=w
      VL[i]=v


  def dfs(W,i):
      if i==N:
          return 0
      if dp[W][i]:
          return dp[W][i]
      if W-WL[i]>=0:
          dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
          return dp[W][i]
      else:
          dp[W][i]=dfs(W,i+1)
          return dp[W][i]

  print((dfs(W,0)))

main()


# Optimized solution
def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

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

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print((dp[-1][-1]))
main()
# Original solution

def knapsack1(N,W,H,max_W):
    #print(W,H,max_W)
    #print(H[1][0],H[1][1])
    DP = [[0]*(max_w+1) for i in range(N+1)]
    #print(DP[0][0],DP[0][1])
    for i in range(N):
        for j in range(max_w+1):
            if j-H[i][0] >= 0:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j-H[i][0]]+H[i][1])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
        #print(DP)
    #print(DP)
    return DP 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = list(map(int,input().split()))
    H = [[0]*2 for i in range(N)]
    max_w = 0
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
        max_w += lst[0]
    ans = knapsack1(N,W,H,max_w)
    finlst = []
    finans = 0
    for i in range(N+1):
        #print(ans[i][W])
        maxr = max(ans[i][:W+1])
        if maxr > finans:
            finans = maxr
    print(finans)
    #print(lstx)
    #print(max(ans[-1]))
    

# Optimized solution

def knapsack1(N,W,weight,value):
    inf = float("inf")
    DP = [[-inf]*(W+1) for i in range(N+1)]
    for i in range(W+1): DP[0][i]=0

    for i in range(N):
        for j in range(W+1):
            if j-weight[i] >= 0:
                DP[i+1][j] = chmax(DP[i][j],DP[i][j-weight[i]]+value[i])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
    return DP[N][W] 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = list(map(int,input().split()))
    weight = [0]*N
    value = [0]*N
    #print(weight,value)
    for i in range(N):   
        lst = list(map(int,input().split()))
        #print(lst)
        weight[i] = lst[0]
        value[i] = lst[1]
        #max_w += lst[0]
    #print(weight,value)
    ans = knapsack1(N,W,weight,value)
    print(ans)
    #print(max(max(ans)))
    #print(max(ans[-1]))
# Original solution

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = list(map(int, input().split()))
    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

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = list(map(int, input().split()))
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

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

for i in range(N):
    w, v = list(map(int, input().split()))
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        dp[weight][item] = max([dp[weight][item]] + 
                               [values[item-1] + dp[weight - weights[item-1]][j] for j in range(item)])

        dp[weight][item] = max(dp[weight-1][item], dp[weight][item])
    
print((max(dp[-1])))


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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

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

for i in range(N):
    w, v = list(map(int, input().split()))
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):

        # Case: dont include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item-1])

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight-1][item])
        
        if weights[item-1] > weight: continue
 
        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])
    
print((max(dp[-1])))
# Original solution
def solve(items, n, w):
    f = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i-1]
        for j in range(w + 1):
            f[i][j] = f[i-1][j]
            if j >= wi:
                f[i][j] = max(f[i][j], f[i-1][j-wi] + vi)
    return f[n][w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print((solve(items, n, w)))


if __name__ == '__main__':
    main()


# Optimized solution
def solve(items, n, w):
    dp = [0] * (w+1)
    for i in range(n):
        wi, vi = items[i]
        for j in range(w, wi-1, -1):
            dp[j] = max(dp[j], dp[j-wi] + vi)

    return dp[w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print((solve(items, n, w)))


if __name__ == '__main__':
    main()
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=list(map(int,input().split()))
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        dp[j]=max(dp[j],dp[j-w]+v) 
    
print((max(dp)))


# Optimized solution
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=list(map(int,input().split()))
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print((max(dp)))
# Original solution
import sys
input=sys.stdin.readline
 
n,w=list(map(int,input().split()))
dp=[0]*(w+1)
c,p=list(map(int,input().split()))
dp[c]=p
 
def ans(n,w):
  for _ in range(1,n):
    c,p=list(map(int,input().split()))
    for j in range(w,c-1,-1):
      if dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
  return max(dp)
print((ans(n,w)))

# Optimized solution
import sys
input=sys.stdin.readline
 
n,w=list(map(int,input().split()))
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=list(map(int,input().split()))
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print((ans(n,w)))
# Original solution
import sys
input=sys.stdin.readline
 
n,w=list(map(int,input().split()))
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=list(map(int,input().split()))
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print((ans(n,w)))

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

n,w=list(map(int,input().split()))
dp=[0]*(w+1)
c,p=list(map(int,input().split()))
dp[c]=p

def ans(n,w):
  for _ in range(1,n):
    c,p=list(map(int,input().split()))
    for j in range(w,c,-1):
      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
    if dp[c] < p:
      dp[c]=p
  return max(dp)
print((ans(n,w)))
# Original solution
N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

def dp(f,w):
    global F
    if w < 0:
        return -10**9
    if f == 0:
        if w < F[0][0]:
            return 0
        else:
            return F[0][1]
    return max(dp(f-1,w),dp(f-1,w-F[f][0])+F[f][1])

print((dp(N-1,W)))

# Optimized solution
N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print((DP[-1]))
# Original solution
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().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 sum_w in range(K + 1):
        for i in range(N):
            if sum_w - W[i] < 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[i]] + V[i]
                )
    print((dp[-1][-1]))


main()


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


def read_ints():
    return list(map(int, read().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()