There are N items with weights $$$w_i$$$ and values $$$e_i$$$. We need to choose some items such that sum of their values($$$e_i$$$) is equal to X and sum of their weights($$$w_i$$$) is minimum. The values of items are given as exponents 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≤e_i≤999$$$(Exponent of the value of the item)
$$$1≤w_i≤10^9$$$(Weight of the item)
example :
input:
5 34
0 1
0 2
0 3
1 25
5 12
output:
15
