P4653 [CEOI 2017] Sure Bet

Luck is a fundamental part of betting. Some people improve their chances and earnings by having good knowledge of what they are betting on. We will take a different approach. Various bookmakers offer different *odds* or quotas for the same outcome. (An *odds* of $x$ means that if you bet 1 euro and predict the outcome correctly, you get $x$ euros back. If you predict the outcome incorrectly, you of course get nothing back. Note that you pay 1 euro regardless of the outcome.) What if you could be certain of making a profit by cleverly placing several bets? You would want to make this guaranteed profit as large as possible. The event we want to bet on has two possible outcomes. There are $n$ bookmakers that offer different odds. Let us denote the odds offered by the $i$-th bookmaker for the first outcome with $a_i$, and the odds offered for the second outcome with $b_i$. You can place a bet on any subset of the offered odds. You can even bet on both outcomes at the same bookmaker. However, all bets have to be exactly 1 euro and you cannot bet on the same outcome with the same bookmaker multiple times. In case of the first outcome, you will receive $a_i$ euros from every bookmaker $i$ with whom you placed a bet on the first outcome. Similarly, in case of the second outcome, you will receive $b_i$ euros from all eligible bookmakers. Of course in both cases, you already paid 1 euro for every bet you placed. What is the largest *guaranteed* profit (i.e. regardless of the outcome) if you place your bets optimally?

The first line contains the number of bookmakers, $n$. The following $n$ lines describe the odds offered by each bookmaker with two space-separated real numbers $a_i$ and $b_i$ - the odds for the first and second outcome offered by the $i$-th bookmaker. The odds will be given to at most 4 decimal places.

Output the maximum guaranteed profit rounded to exactly 4 decimal places.

#### Comment The optimal betting strategy consists of betting on the second outcome with the first bookmaker and on the first outcome with the third and fourth bookmaker. In case of the first outcome, we will earn $1.6 + 1.9 − 3 = 0.5$ and in case of the second outcome $3.7 − 3 = 0.7$. So we’re guaranteed 0.5 euros regardless of the outcome. #### Constraints - $1.0 \le a_i, b_i \le 1000.0$ - $1 \le n \le 100\ 000$ ##### Subtask 1 (20 points) - $n \le 10$ ##### Subtask 2 (40 points) - $n \le 1\ 000$ ##### Subtask 3 (40 points) - no additional constraints