UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4570. [Scoi2016]妖怪

统计 下载数据

Description

邱老师是妖怪爱好者,他有n只妖怪,每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师,于
是他从真新镇出发,踏上未知的旅途,见识不同的风景。环境对妖怪的战斗力有很大影响,在某种环境中,妖怪可
以降低自己k×a点攻击力,提升k×b点防御力或者,提升自己k×a点攻击力,降低k×b点防御力,a,b属于正实数
,k为任意实数,但是atk和dnf必须始终非负。妖怪在环境(a,b)中的战斗力为妖怪在该种环境中能达到的最大攻击
力和最大防御力之和。strength(a,b)=max(atk(a,b))+max(dnf(a,b))环境由a,b两个参数定义,a,b的含义见前
文描述。比如当前环境a=3,b=2,那么攻击力为6,防御力为2的妖怪,能达到的最大攻击力为9,最大防御力为6。
所以该妖怪在a=3,b=2的环境下战斗力为15。因此,在不同的环境,战斗力最强的妖怪可能发生变化。作为一名优
秀的妖怪训练师,邱老师想发掘每一只妖怪的最大潜力,他想知道在最为不利的情况下,他的n只妖怪能够达到的
最强战斗力值,即存在一组正实数(a,b)使得n只妖怪在该环境下最强战斗力最低。

Input

第一行一个n,表示有n只妖怪。接下来n行,每行两个整数atk和dnf,表示妖怪的攻击力和防御力。
1≤n≤10^6, 0<atk,dnf≤10^8

Output

 输出在最不利情况下最强妖怪的战斗力值,保留4位小数。

Sample Input

3
1 1
1 2
2 2

Sample Output

8.0000

Hint

Source