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

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

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)

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