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.