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$$$:
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?
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
Name |
---|