p02321 Huge Knapsack Problem
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
```python

from bisect import bisect_right


def main():

    N,W = map(int, input().split())
    wv = []
    for _ in range(N):
        v,w = map(int, input().split())
        wv.append([w,v])

    d1 = [[0,0]]
    d2 = [[0,0]]
    half = N // 2

    for i in range(half):
        w,v = wv[i]
        size = len(d1)
        # i-1までに作っている組について、iを足すパターンを加える
        for j in range(size):
            d1.append([d1[j][0] + w, d1[j][1] + v])

    for i in range(N - half):
        w,v = wv[half + i]
        size = len(d2)
        for j in range(size):
            d2.append([d2[j][0] + w, d2[j][1] + v])

    d1.sort()
    d2.sort()

    # i+1番目はiより重いが、iより価値が低いなら、i+1の重さまででiの価値ができるやで、に塗り替える
    for i in range(len(d2) - 1):
        if d2[i+1][1] < d2[i][1]:
            d2[i+1][1] = d2[i][1]

    ans = 0
    INF = float("inf")
    for w,v in d1:
        if w > W:
            continue

        rest = W - w
        idx = bisect_right(d2, [rest, INF])
        ans = max(ans, d2[idx - 1][1] + v)

    print(ans)

if __name__ == "__main__":
    main()

```