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.