Door of the Ancient

Pandy is at the last stage of "Door of the Ancients", his favorite video game. His objective is to pass through a sacred door. There are two ways to do this: by defeating a mighty guardian and snatching the key to the sacred door, or by destroying the sacred door (with brute force) directly.

Pandy has no confidence in fighting the mighty guardian, so he opts for the second method. Pandy has N items that can be thrown at the sacred door. Each item originally has a power of Pi and a value of Vi. If Pandy throws the ith item at the sacred door, the following happens in order:

1. The sacred door's durability decreases by the ith item's current power.
2. The ith item's power doubles.
3. The ith item's value is halved (rounded down).

The same item can be thrown at the sacred door repeatedly as long as its value is not zero.

Originally, the sacred door has a durability of H. Pandy must decrease this durability to zero or below (H ≤ 0) by throwing one or more items to destroy the sacred door.

Unfortunately, the player's score in this game is also determined by the total value of all items the player owns at the end of the game (that is why fighting the mighty guardian is popular among other players). Therefore, help Pandy determine the minimum loss of the total value of all items to destroy the sacred door.

For example, let H = 100, N = 3, P1..3 = {10, 75, 50}, and V1..3 = {2, 10, 50}.

To destroy the sacred door, Pandy can throw the second item twice:

• Throw the 2nd item: H decreases by 75, P2 doubles to 150, and V2 halves to 5 (loss of 5).
• Throw the 2nd item: H decreases by 150, P2 doubles to 300, and V2 halves to 2 (loss of 3).

The total damage to the sacred door is 75 + 150 = 225, more than enough to destroy it (original H = 100). The loss of the total value of all items is 5 + 3 = 8.

Alternatively, Pandy can throw the first item twice and the second item once:

• Throw the 1st item: H decreases by 10, P1 doubles to 20, and V1 halves to 1 (loss of 1).
• Throw the 1st item: H decreases by 20, P1 doubles to 40, and V1 halves to 0 (loss of 1). This item can no longer be used.
• Throw the 2nd item: H decreases by 75, P2 doubles to 150, and V2 halves to 5 (loss of 5).

The total damage to the sacred door is 10 + 20 + 75 = 105, and the loss of the total value of all items is 1 + 1 + 5 = 7. In this example, there is no way to destroy the sacred door with a loss of the total value of all items less than 7.

The input begins with a line containing two integers: N H (1 ≤ N ≤ 100; 1 ≤ H ≤ 10^9), the number of available items and the sacred door's original durability, respectively. The next N lines each contain two integers: Pi Vi (1 ≤ Pi ≤ 10^9; 1 ≤ Vi ≤ 100), the original power and value of the ith item, respectively.

Output a single integer on one line: the minimum loss of the total value of all items to destroy the sacred door, or -1 if it is impossible to destroy the sacred door.