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