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

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

-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 +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 -    n, w = list(map(int, input().split())) -    r = woo(n, w) -    print((max(r))) +    main()