邱老师是妖怪爱好者，他有 $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$ 只妖怪在该环境下最强战斗力最低。
Comet OJ