There are N items with weights Wi 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