Chemical Experiment

Time limit2sMemory limit128 MB

Summary

Given bottles with known concentrations and volumes, find the maximum volume of an exact target-concentration mixture obtainable by taking any partial amounts from each bottle.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math
Solved: No attempts yet

Problem

In chemistry, a solution has a different meaning from a solution in computer programming.

If x liters of a substance are mixed with (100 - x) liters of water, the result is 100 liters of an x% solution of that substance.

Dasom has N bottles containing solutions of the same substance. Each bottle has a label showing how much solution it contains and what its concentration is.

Dasom wants to choose any amounts from these bottles and combine them into one bottle to make a solution whose concentration is exactly M%. A whole bottle does not have to be used; any partial amount may be taken and mixed.

Find the maximum number of liters of M% solution that can be made.

Input

The first line contains the number of bottles N and the target concentration M.

N is a positive integer not greater than 50, and M is a nonnegative integer not greater than 100.

Each of the next N lines contains the information for one bottle. Each line gives the concentration written on the label and the amount of solution in the bottle, separated by a space. The concentration is a nonnegative integer not greater than 100, and the amount of solution is a positive integer not greater than 1000.

Output

Print the maximum amount, in liters, of M% solution that can be made.

An absolute or relative error of at most 10^-2 is accepted.

Hint

A solution below the target concentration contributes a deficit of substance, while a solution above the target concentration contributes an excess. The mixture reaches the target concentration exactly when the total deficit and total excess are balanced.

Examples5

Example 1
Input
```
2 50
0 20
100 30
```
Expected output
```
40.00
```
Example 2
Input
```
2 60
0 20
100 30
```
Expected output
```
50.0
```
Example 3
Input
```
3 50
90 10
70 10
80 10
```
Expected output
```
0.0
```

Example 4

Input

Expected output

35.18518518518519

Example 5
Input
```
3 50
50 395
50 971
50 964
```
Expected output
```
2330.0
```