Sure Bet

Luck carries a lot of weight in betting. Some people raise their hit rate and their winnings by knowing the event well. Here we take a different route.

Bookmakers quote different odds on the same outcome. Odds of $x$ mean that if you stake 1 euro and the outcome you picked happens, you get $x$ euros back. If it does not happen, you get nothing back. You pay 1 euro for every bet you place, whatever the outcome is. If clever bets spread over several bookmakers lock in a profit no matter which outcome happens, you want that locked profit to be as large as possible.

The event has two possible outcomes. There are $n$ bookmakers quoting different odds. Let $a_i$ be the odds the $i$-th bookmaker quotes on the first outcome and $b_i$ the odds it quotes on the second outcome. You may bet on any subset of the quoted odds, and you may bet on both outcomes at the same bookmaker. Every bet is exactly 1 euro, and you cannot bet on the same outcome at the same bookmaker more than once.

If the first outcome happens, you receive $a_i$ euros from every bookmaker $i$ where you bet on the first outcome. If the second outcome happens, you receive $b_i$ euros from every bookmaker $i$ where you bet on the second outcome. In both cases you have already paid 1 euro for every bet you placed.

Find the largest profit that is guaranteed regardless of the outcome when you bet optimally.

The first line contains the number of bookmakers $n$. Each of the next $n$ lines contains two space-separated real numbers $a_i$ and $b_i$, the odds the $i$-th bookmaker quotes on the first outcome and on the second outcome. The odds are given with at most 4 decimal places.

Print the largest guaranteed profit on one line, rounded to exactly 4 decimal places.

• $1 \le n \le 100000$
• $1.0 \le a_i, b_i \le 1000.0$

In the first example the best plan is to bet on the second outcome at bookmaker 1 and on the first outcome at bookmakers 3 and 4. That is three bets, so you pay 3 euros. The first outcome earns $1.6 + 1.9 - 3 = 0.5$ euros and the second outcome earns $3.7 - 3 = 0.7$ euros, so 0.5 euros is guaranteed either way.