You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 40
* 1 ≤ vi ≤ 1015
* 1 ≤ wi ≤ 1015
* 1 ≤ W ≤ 1015

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9
from typing import Tuple, List
from heapq import heappush, heappop


def max_value(max_weight: int, items: List[Tuple[int, int]]) -> float:
    def _cost(weight: int, value: int, i: int) -> Tuple[int, float]:
        # Use value as negative cost
        for j in range(i, n):
            v, w = items[j]
            if (weight + w > max_weight):
                return (-value, -value - (v / w) * (max_weight - weight))
            weight += w
            value += v
        return (-value, -value * 1.0)

    n = len(items)
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if (cost > maxcost):
            break
        if (i < n):
            v, w = items[i]
            if (weight + w <= max_weight):
                heappush(heap, (cost, upper, weight + w, value + v, i + 1))
            u, c = _cost(weight, value, i + 1)
            if (c < maxcost):
                if (u < maxcost):
                    maxcost = u
                heappush(heap, (c, u, weight, value, i + 1))

    return -maxcost


if __name__ == '__main__':
    N, W = map(lambda x: int(x), input().split())
    items: List[Tuple[int, int]] = []

    for _ in range(N):
        v, w = map(lambda x: int(x), input().split())
        items.append((v, w))

    print(max_value(W, items))

