from pathlib import Path

txt = Path("rucsac.in").read_text().split('\n')
txt = [ [int(x) for x in t.split()] for t in txt ]
#print(txt)

n = int(txt[0][0])
g = int(txt[0][1])
#print(n,g)

v = [0]*(g+1)
#print(v)
for greutate,profit in txt[1:n+1]:
    for x in range(g,-1,-1):
        if x-greutate >=0:
            v[x] = max(v[x],v[x-greutate]+profit)

Path("rucsac.out").write_text(str(v[-1]))