410608: GYM104065 D Gambler's Ruin

The football match between Bobo United (BU) and Bobo City (BC) is about to start. As an odds compiler working for a gambling company, Bobo needs to set odds for each team.

There are $$$n$$$ gamblers ready to gamble on this game, and each has an estimated $$$p_i$$$ of BU's probability of winning. Here, we consider the setting that the gambling company previously collects all gamblers' information, so each $$$p_i$$$ is known.

If you set odd $$$x$$$ for BU and odd $$$y$$$ for BC, then for each gambler $$$i$$$:

• if $$$p_i\cdot x\geq 1$$$, he/she will bet $$$c_i$$$ dollars on BU.
• otherwise, if $$$(1-p_i)\cdot y\geq 1$$$, he/she will bet $$$c_i$$$ dollars on BC.

Suppose the total amount of money bet on BU is $$$s_{x}$$$ dollars and the total amount of money bet on BC is $$$s_y$$$ dollars. If BU eventually wins the match, the company needs to pay out $$$s_x\cdot x$$$ dollars; if BC wins, the company needs to pay out $$$s_y\cdot y$$$ dollars. In the worst case, the profit of the gambling company is $$$s_x+s_y-max(s_x\cdot x,s_y\cdot y)$$$ dollars (the profit might be negative, meaning the company actually loses money).

Bobo needs to set the value of $$$x$$$ and $$$y$$$ to maximize the profit in the worst case, or otherwise, he might be fired by the company. Can you help him?

An example of pot odds offered by the online gambling company. Source: some mysterious website

The first line contains an integer $$$n$$$ $$$(1\leq n\leq 10^6)$$$, denoting the number of gamblers.

The $$$n$$$ lines follow. The $$$i$$$-th $$$(1\leq i\leq n)$$$ line contains a real number $$$p_i$$$ and an integer $$$c_i$$$ $$$(0\leq p_i\leq 1,1\leq c_i\leq 10^8)$$$. with meaning already given in the statement. It is guaranteed $$$p_i$$$ contains at most $$$6$$$ digits after the decimal point.

Output a number in one line, denoting the maximum profit the gambling company can get in the worst case by optimally setting the value of $$$x$$$ and $$$y$$$. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer will be considered correct if $$$\frac{|a-b|}{\max(b,1)}\leq 10^{-6}$$$.

2
1 15
0 10

10.0000000000

3
0.4 100
0.5 100
0.6 100

33.3333333333