P3291 [SCOI2016] 妖怪

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

无

无

对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\lt \mathrm{atk},\mathrm{dnf}\le 10^8$。 Statement fixed by Starrykiller.