Şehmettin wants to buy a cabbage. To buy the cabbage he needs to go to the grocer who never gives back any change. So Şehmettin needs to give the exact cost of the cabbage otherwise he would get duped by the grocer. Şehmettin lives in Doodleland where every coin/banknote has the value of a power of 2 from \(2^0\) to \(2^\infty\). This currency is called a Doodle. Even though two Doodles have the same value, they may weigh differently. For example a 8 Doodle can be either 1 gram or a thousand. The cabbage costs \(\mathbf{X}\) doodles. Şehmettin has \(\mathbf{N}\) currencies of different values and weights. Help Şehmettin carry the lightest amount of money that sums up to the cost of the cabbage.

• Since representing a number like \(2^{999}\) would take a lot of space and is unnecessary, the values of the currencies are represented by their exponent.
• If the currency is \(2^0\)=1: 0
• If the currency is \(2^3\)=8: 3
• If the currency is \(2^{999}\): 999

Input

• The first line contains \(2\) integers:
  • \(2\leq\mathbf{N}\leq10^7\) (The number of coins/banknotes Şehmettin has with him)
  • \(1\leq\mathbf{X}<2^{1000}\) (The cost of the cabbage)
• The next \(\mathbf{N}\) lines contain 2 integers:
  • \(0\leq\mathbf{e_i}\leq999\) (Exponent of the Value of the currency)
  • \(1\leq\mathbf{w_i}\leq10^9\) (Weight of the currency)

Output

• Print \(-1\) if there is no solution.
• Print sum of the weights of the currencies otherwise.

Example

Input 1:

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

Output 1:

15

Input 2:

5 35
0 1
0 2
0 3
1 25
5 12

Output 2:

18

Input 3:

5 5000
0 1
0 2
0 3
1 25
5 12

Output 3:

-1

Explanation

Input 1: Using 1st, 2nd and 5th currencies:

• Value: \(2^0+2^0+2^5=34\)
• Weight: \(1+2+12=15\)