CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    n,w=list(map(int,input().split()))
    wv=[]
    for _ in range(n):
        wv.append(list(map(int,input().split())))
    dp=[]
    temp=[]
    for i in range(0,w+1):
        if i < wv[0][0]:
            temp.append(0)
        else:
            temp.append(wv[0][1])
    # print(temp)
    dp.append(temp)
    # print(dp)

    for i in range(1,n):
        temp=[]
        for j in range(0,w+1):
            if j < wv[i][0]:
                temp.append(dp[i-1][j])
            else:
                if j-wv[i][0] >=0:
                    temp.append(max(dp[i-1][j],dp[i-1][j-wv[i][0]] + wv[i][1]))
                else:
                    temp.append(dp[i-1][j])
        # print('temp')
        # print(temp)
        dp.append(temp)
        # print('dp')
        # print(dp)
    print((dp[n-1][w]))

if __name__=='__main__':
    main()


# Optimized solution
def main():
    n,lim_w=list(map(int,input().split()))
    wv = []
    for _ in range(n):
        tmp = list(map(int,input().split()))
        wv.append(tmp)
    dp = [[0] * (lim_w+1) for i in range(n+1)]

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

    print((dp[n][lim_w]))
if __name__=='__main__':
    main()
# Original solution
N,W=list(map(int,input().split()))
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  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(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    #dp[i][j]=max(dp[i][j],dp[i-1][j])
    #if j-w[i]<0: continue
    #dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
    if j-w[i]<0:
      dp[i][j]=max(dp[i][j],dp[i-1][j])
    else:
      dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i-1][j-w[i]]+v[i])

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


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

#print(dp)
print((dp[N][W]))
# Original solution
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[-1]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = list(map(int, input().split()))
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print(("Case #{}: {}".format(testcase + 1, result)))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


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

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


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


# Optimized solution
N, W = list(map(int, input().split()))
dp = [[0]*(W+1) for _ in range(N)]
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))
for i in range(N):
    for k in range(1,W+1):
        if w[i] <= k:
            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-1][W]))
# Original solution
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (N + 1) for _ in range(W+1)]

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

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(1, W+1):
            if j - w[i] >= 0:
                dp[i+1][j] = max(
                    dp[i][j],
                    dp[i+1][j-1],
                    dp[i][j-w[i]] + v[i]
                )
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()
# Original solution
[n,w] = [int(i) for i in input().split()]
wei_val = []
for i in range(n):
    wei_val.append([int(j) for j in input().split()])
"""
dp[i][w_zantei] = v
i : i番目までの品物
w_zantei : 合計の重さがこれになる
v : 価値

更新式
dp[i][w_zantei] = max(dp[i][w_zantei],dp[i - 1][w_zantei - wei_val[0]] + wei_val[1]) (if w >= w_zantei+wei_val[i][0])
dp[i][w_zantei] = dp[i-1][w_zantei] (if w < w_zantei+wei_val[0])
"""
dp = [[0]* (w+1) for i in range(n)]
for i in range(n):
    for w_zantei in range(w+1):
        if w_zantei >= wei_val[i][0]:
            dp[i][w_zantei] = max(dp[i-1][w_zantei],dp[i - 1][w_zantei - wei_val[i][0]] + wei_val[i][1])
        else:
            dp[i][w_zantei] = dp[i-1][w_zantei]
print((dp[n-1][w]))


# Optimized solution
[n,w] = [int(i) for i in input().split()]
dp = [[0]*(w+1) for i in range(n)]
wv = []
for i in range(n):
    wv.append([int(j) for j in input().split()])
"""
dp[i][w] = v
i : i番目まで
w : それまでの合計
"""

for i in range(n):
    for j in range(w+1):
        if i == 0:
            dp[i][wv[i][0]] = wv[i][1]
        else:
            if j - wv[i][0] >= 0:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j - wv[i][0]]+wv[i][1])
            else:
                dp[i][j] = dp[i-1][j]
print((max(dp[n-1])))
#print(dp)
# Original solution
import sys
input =sys.stdin.readline 
number, weight = input().rstrip().split()
number = int(number)
weight = int(weight)

items = [list(map(int,input().rstrip().split())) for _ in range(number)]
#print(items)
dp = [[0]*(weight+1) for _ in range(number+1)]

for i in  range(number):
    for j in range(weight+1):
        if j < items[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-items[i][0]] + items[i][1])

print((dp[number][weight]))


# 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
import sys
sys.setrecursionlimit(10**8)

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

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

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    dp[n][w]= max([r1,r2])
    return dp[n][w]

print((calc(N-1,0)))

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

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

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

for i in range(N):
    for j in range(0,W+1):
        if (j-wv[i][0])>=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[N][W]))
# Original solution
import sys


def main():
    input = sys.stdin.readline

    N, W = list(map(int, input().split()))
    dp = [0] * (W + 1)

    WV = (list(map(int, input().split())) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print((dp[-1]))


main()


# Optimized solution
import sys


def main():
    input = sys.stdin.readline

    N, W = list(map(int, input().split()))
    dp = [0] * (W + 1)

    WV = (list(map(int, input().split())) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[-1]))


main()
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(W + 1)[::-1]:
            if i - w >= 0:
                tmp = dp[i - w] + v
                if tmp > dp[i]:
                    dp[i] = tmp

    print((max(dp)))


if __name__ == "__main__":
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(w, W + 1)[::-1]:
            tmp = dp[i - w] + v
            if tmp > dp[i]:
                dp[i] = tmp

    print((max(dp)))


if __name__ == "__main__":
    main()
# Original solution
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print((max(t.values())))


# Optimized solution
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      t[nw] = nv
print((max(t.values())))
# Original solution
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      updates.append([nw, nv])
  for u in updates:
    t[u[0]] = u[1]
print((max(t.values())))


# Optimized solution
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      updates.append([nw, nv])
  for u in updates:
    t[u[0]] = u[1]
print((max(t.values())))
# Original solution
from functools import cmp_to_key

def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
  t = {}
  t[w] = 0
  for i in range(n):
    keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
    tw, tv = d[i]
    for j in keys:
      nw = j - tw
      if nw < 0:
        continue
      nv = t[j] + tv
      if nw in t:
        if nv > t[nw]:
          for k in list(t.keys()):
            if k < nw and t[k] <= nv:
              del t[k]
          t[nw] = nv
      else:
        Flag = False
        for k in t:
          if nw < k and nv <= t[k]:
            Flag = True
            break
        if Flag:
          continue
        for k in list(t.keys()):
          if k < nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
  print((max(t.values())))

main()

# Optimized solution
def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print((max(t)))
main()
# Original solution
def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  t = {}
  t[w] = 0
  for i in range(n):
    keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
    tw, tv = d[i]
    for j in keys:
      nw = j - tw
      if nw < 0:
        continue
      nv = t[j] + tv
      if nw in t:
        if nv > t[nw]:
          t[nw] = nv
      else:
        t[nw] = nv
  print((max(t.values())))
main()


# Optimized solution
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = [int(e) for e in readline().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in readline().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print((max(t)))
main()
# Original solution
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = [int(e) for e in readline().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in readline().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print((max(t)))
main()

# Optimized solution
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = list(map(int, readline().split()))
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = list(map(int, readline().split()))
    for i in range(nw, w + 1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i - nw] < ti + nv:
        t[i - nw] = ti + nv
  print((max(t)))
main()
# Original solution
# DP
def main():
    from builtins import int, map, max, min, range
    from sys import stdin
    readline = stdin.readline

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = list(map(int, readline().split()))
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print((max(dp)))


main()


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

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


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

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


main()


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

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


main()
# Original solution
# DP
N, W = list(map(int, input().split()))

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


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

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


main()
# Original solution
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
WV = (list(map(int, input().split())) for _ in range(N))

DP = [0] * (W+1)

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


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

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print((dp()))
# Original solution
import sys
input=sys.stdin.readline

n, cap = list(map(int, input().split()))
val =[0]*(cap+1)
for _ in range(n):
    w, v = list(map(int, input().split()))
    for wk in range(cap,w-1,-1):
        nv=val[wk-w]+v
        if val[wk]<nv:
            val[wk]=nv
print((val[-1]))


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

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

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


# Optimized solution
import sys

input = sys.stdin.readline


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


n, cap = list(map(int, input().split()))
print((nap(n, cap)))
# Original solution
import sys
input=sys.stdin.readline

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i, (w, v) in enumerate(wv):
        dp[i + 1][:w] = dp[i][:w]
        for j, (v1, v2) in enumerate(zip(dp[i], dp[i][w:])):
            nv = v1 + v
            if nv > v2:
                dp[i + 1][j + w] = nv
            else:
                dp[i + 1][j + w] = v2
    print((dp[-1][-1]))

n, W = list(map(int, input().split()))
f(n,W)


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

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [-1] * (W + 1)
    dp[0] = 0
    for w, v in wv:
        for i in range(W - w, -1, -1):
            if dp[i] == -1: continue
            nv = dp[i] + v
            if nv > dp[i + w]:
                dp[i + w] = nv
    print((max(dp)))

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

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i,j):
    if i>=n:
        return 0

    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    return val

print((solve(0,w)))

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

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

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

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