# ## read the cost matrix 
# import heapq
# with open('date.in', 'r') as f:
#     c = [[ int(num) if (num != 'inf') else float('inf') for num in line.split(' ')] for line in f]
# print(c)


# class Node: 
#     def __init__(): 


# def row_reduction(matrix, reduction):
#     copy = []
#     for index, row in enumerate(matrix):
#         minElem = min(row)
#         reduction[index] += minElem
#         print ('min elem', minElem, row)
#         copy.append([e-minElem for e in row])
#     return copy


# def column_reduction(matrix, reduction): 
#     copy = []
#     tc = list(zip(*matrix))
#     for index, row in enumerate(tc):
#         print ("have row", row)
#         minElem = min(row)
#         reduction[index] += minElem
#         copy.append([e-minElem for e in row])
#     return list(zip(*copy))



# def get_lower_bound(matrix): 
#     cost = 0

#     rows = [0] * len(c)
#     columns = [0] * len(c[0])

#     rr_matrix = row_reduction(matrix, rows)
#     print (rr_matrix)
#     r_matrix = column_reduction(rr_matrix, columns)

#     print ("rows, columns", rows, columns)
#     return r_matrix
    
# # print(row_reduction(c,rows), rows)
# print (get_lower_bound(c))

# def travel(): 



# input data 
# N, Gmax
# value1, weight1 
# ...
# valueN, weightN 

import heapq
class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]
    
    def empty(self):
        if (len(self._queue) is 0):
            return True
        else:
            return False

    def length(self):
        return len(self._queue)

class Item: 
    def __init__(self, weight, value): 
        self.weight = weight
        self.value = value
        self.bound = bound 
        self.level = 0


class Node: 
    def __init__(self, value = 0, weight = 0, bound = 0, level = -1): 
        self.value = value
        self.weight = weight
        self.bound = bound
        self.level = level

    def create_from_prev(self, previous_node, item):
        self.value = previous_node.value + item.value
        self.weight = previous_node.weight + item.weight
        self.level = previous_node.level + 1



def bound(node, capacity, items): 
    if (node.weight > capacity): 
        return 0
    
    result = node.value
    weight = node.weight

    for item in items[node.level + 1:]: 
        if (item.weight + weight <= capacity):
            result += item.value

    return result

def knapsack(data, capacity): 
    items = sorted(data, key = lambda i: i.weight/i.value)

    start_node = Node(0, 0)
    start_node.bound = bound(start_node, G, items)

    Q = PriorityQueue()
    Q.push(start_node, start_node.bound)


    maxValue = 0
    solution = []

    while not Q.empty(): 
        node = Q.pop()

        if (node.bound > maxValue): 
            next_node = Node()
            next_node.create_from_prev(node, items[node.level + 1])

            if (next_node.weight <= capacity and next_node.value > maxValue): 
                maxValue = next_node.value
            
            next_node.bound = bound(node, capacity, items)


            if (next_node.bound > maxValue): 
                Q.push(next_node, next_node.bound)


            next_node2 = Node(node.value, node.weight, 0, node.level + 1)
            next_node2.bound = bound(node, capacity, items)

            if (next_node2.bound > maxValue): 
                Q.push(next_node2, next_node2.bound)
    
    return maxValue



with open('date.in', 'r') as f:
    # weight, value

    lines = f.readlines()
    global n 
    n = int(lines[0].split(' ')[0])
    global G
    G  = int(lines[0].split(' ')[1])
    data = [Item(int(line.split(' ')[0]), int(line.split(' ')[1])) for line in lines[1:]]

print (knapsack(data, G))