Problem Description

At the annual pig slaughter festival, butcher Bajs is doing the final part of the event: taking out part of his award-winning ham and distributing it to everyone attending.

This year, there are $n$ participants. The $i$-th person has already eaten $a_i$ kilograms of ham. Bajs will distribute his ham in the ratio $b_1:b_2:\cdots:b_n$. In other words, let $S=\sum\limits_{j=1}^nb_j$, then the $i$-th person will receive $\dfrac{b_i}S$ of the total ham weight.

However, Bajs still cannot decide the total amount of ham to take out, because after everyone receives and eats their share, a ranking list will be made according to how many kilograms of ham each person has eaten, from large to small (if two people have eaten the same amount, they are ordered by increasing index), and the first place will be announced as the person of the year. Although Bajs has been bribed many times, he still refuses to change the distribution ratio, saying that he is honest and kind. Bajs has severe OCD, so he wants the indices on the ranking list, from top to bottom, to be exactly $1,2,\cdots,n$. Please help Bajs determine the total amount of ham he should take out to satisfy this requirement.

Input Format

The first line contains an integer $n$, the number of participants.
Then follow $n$ lines, each containing two integers $a_i,b_i$, representing the kilograms of ham already eaten by the $i$-th person and the weight ratio they take in the distribution (see the Description).

Output Format

If no matter how much ham Bajs takes out the requirement cannot be satisfied, output -1.

Otherwise, output a real number $x$, the number of kilograms of ham Bajs takes out. You must ensure:

• $0\leqslant x\leqslant 10^7$.
• $x$ has at most $12$ digits after the decimal point. It is recommended to round your answer before output.

If at least one of the above conditions is not satisfied, your answer will be judged as WA.

If there are multiple solutions, output any one of them. That is, you do not need to minimize the amount of ham Bajs takes out.

3
7 1
3 2
10 0

10.5

3
2 1
4 0
0 3

-1

5
15 4
6 7
12 5
9 6
1 7

87

Hint

[Sample 1 Explanation]

Bajs took out $10.5$ kilograms of ham. Since the distribution ratio is $1:2:0$, the three people receive $3.5$ kilograms, $7$ kilograms, and $0$ kilograms of ham respectively. In the end, they have eaten a total of $10.5$ kilograms, $10$ kilograms, and $10$ kilograms of ham respectively. This satisfies Bajs's requirement.

[Constraints]

For all testdata, $2\leqslant n\leqslant 1000$, $0\leqslant a_i,b_i\leqslant 10^6$.

[Source]

This problem is from COCI 2013-2014 CONTEST 3 T4 KOLINJE. With the original test configuration, the full score is $120$ points.

Translated and整理 (zhengli) by Eason_AC.

Suggestions for improving the checker of this problem are welcome.

Translated by ChatGPT 5