# 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('rucsac.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))