There are N items with weights $$$w_i$$$ and values Ei. We need to choose some items such that sum of their values(ei) is X and sum of their weights(wi) is minimum. The values of items are given as exponent of 2.

The first line contains 2 integers:\ 2≤N≤10^7(number of items)\ 1≤X<2^1000(target sum of values)\

The next N lines contain 2 integers:
0≤ei≤999(Exponent of the value of the item)
1≤wi≤10^9(Weight of the item)

example :

input:
5 34
0 1
0 2
0 3
1 25
5 12

output: 15