#!/usr/bin/env python

indat = [int(x) for x in input().split()]
values = list()
weights = list()
for i in range(indat[0]):
    tmp = [int(x) for x in input().split()]
    values.append(tmp[0])
    weights.append(tmp[1])

def rec(i,j):
    if i == len(weights):
        res = 0
    elif j < weights[i]:
        res = rec(i+1,j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-weights[i]) + values[i])
    return res

print(rec(0, indat[1]))