Oil

Interview

Time limit2sMemory limit1024 MB

Summary

Given dollars and euros and n countries that each sell oil for a fixed dollar price or a fixed euro price, find the maximum barrels buyable when each country must be paid in a single currency.

Level: Medium5 of 10
Topics: Greedy, Sorting, Math, Binary search
Solved: No attempts yet

Problem

The president of a small but very proud country has just learned that the twenty-first century is here and that riding horses is no longer fashionable. It turns out, however, that the country has no oil, and cars cannot run without gasoline. So oil will have to be bought from other countries.

A study of the foreign market showed that there are $n$ countries in the world that export oil. The $i$ -th state sells a barrel of oil either for $a\_i$ dollars or for $b\_i$ euros.

The president has $a$ dollars and $b$ euros. The chief accountant says that if one tries to buy oil from a single state with both dollars and euros, the bureaucracy may delay the purchase for a long time, which the president certainly does not want.

Help the president figure out, under these difficult conditions, how many barrels of oil he can buy.

Input

The first line of the input file contains three integers: $n$ , $a$ , and $b$ ( $1 \le n \le 100$ , $0 \le a, b \le 1000$ ). The next $n$ lines contain pairs of numbers $a\_i$ , $b\_i$ ( $1 \le a\_i, b\_i \le 1000$ ).

Output

Print the maximum amount of oil the president can buy. Print the answer with at least two digits after the decimal point.

Examples2

Example 1
Input
```
3 2 5
6 4
3 5
8 7
```
Expected output
```
1.92
```
Example 2
Input
```
4 3 2
1 1
2 2
3 3
4 4
```
Expected output
```
4.00
```