#2015. 「SCOI2016」妖怪

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

邱老师是妖怪爱好者,他有 n 只妖怪,每只妖怪有攻击力 \text{atk} 和防御力 \text{dnf} 两种属性。邱老师立志成为妖怪大师,于是他从真新镇出发,踏上未知的旅途,见识不同的风景。环境对妖怪的战斗力有很大影响,在某种环境中,妖怪可以降低自己 ka 点攻击力,提升 kb 点防御力或者,提升自己 ka 点攻击力,降低 kb 点防御力。 a, b 属于正实数, k 为任意实数,但是 \text{atk} \text{dnf} 必须始终非负。

妖怪在环境 (a, b) 中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和, \text{strength}(a, b) = \max(\text{atk}(a, b)) + \max(\text{dnf}(a, b)) 。环境由 a, b 两个参数定义, a, b 的含义见前文描述。比如当前环境 (a = 3, b = 2) ,那么攻击力为 6 ,防御力为 2 的妖怪,能达到的最大攻击力为 9 ,最大防御力为 6 。所以该妖怪在 (a = 3, b = 2) 的环境下战斗力为 15 。因此,在不同的环境,战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师,邱老师想发掘每一只妖怪的最大潜力,他想知道在最为不利的情况下,他的 n 只妖怪能够达到的最强战斗力值,即存在一组正实数 (a, b) 使得 n 只妖怪在该环境下最强战斗力最低。

输入格式

第一行一个 n ,表示有 n 只妖怪。
接下来 n 行,每行两个整数 \text{atk} \text{dnf} ,表示妖怪的攻击力和防御力。

输出格式

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

样例

样例输入

3
1 1
1 2
2 2

样例输出

8.0000

数据范围与提示

1 \leq n \leq 10 ^ 6, 0 < \text{atk}, \text{dnf} \leq 10 ^ 8