Problem E
Polly Gone

Polly, the programming parrot, has escaped. As Johan is in desperate need for some programming skill, he wants to find her. The only clue that Johan has about the escape route is that Polly flew into his kitchen.

Johan has $N$ boxes on his kitchen table, and each box has a certain probability to contain the parrot. Each box also requires a certain amount of energy in order to be opened. Checking all the boxes would for sure find the disobedient parrot, but there is a problem. Johan is a very lazy person, and he wants to spend as little energy as possible while trying to find Polly. Aware of his own laziness, Johan decided that he will be satisfied with finding the parrot with at least probability $P$, as long as he minimizes the energy wasted in opening boxes. Can you help him?

Input

Input starts with a line with an integer $1 \leq N \leq 10^3$, the number of boxes in Johan’s kitchen and a floating point number $0 \leq P \leq 1$, the minimum probability with which Johan wants to find Polly. Then $N$ lines follow: each line containing an integer $0 \leq e_ i \leq 10^3$ describing the amount of energy needed to open box $i$, and a floating point number $0 \leq p_ i \leq 1$ describing the probability that Polly is inside box number $i$. All probabilities are given with at most four digits after the decimal point.

Output

Output should contain a single integer on a single line: the minimum amount of energy Johan has to waste while finding Polly with at least probability $P$.

2 0.5
2 0.5
1 0.5

1

2 0.5
2 0.51
1 0.49

2

2 1.0
2 0.3291
5 0.6709

7