2271 - 【入门】卡牌游戏 III

通过次数

1

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

a_i 表示这张卡牌的能量值,b_i 表示这张卡牌的魔法值。

周周要从这 n 张卡牌中选出一些形成一个卡组,用这个卡组对敌人造成伤害。一个卡组对敌人的伤害是这个卡组中所有卡牌的能量值之和乘其中魔法值最小的一张卡牌的魔法值。

周周想知道他用一个卡组最多能对敌人产生多少伤害。

输入

第一行,一个正整数 n(1 \leq n \leq 10 ^ 5)

接下来 n 行,每行两个正整数 a_i, b_i(1 \leq a_i, b_i \leq 10 ^ 6)

输出

输出一行,包含一个整数,表示周周用一个卡组对敌人产生的伤害的最大值。

数据范围 对于 70\% 的数据,1 \leq n \leq 10 ^ 3, 1 \leq a_i, b_i \leq 10 ^ 3

对于 100\% 的数据,1 \leq n \leq 10 ^ 5, 1 \leq a_i, b_i \leq 10 ^ 6

样例

输入

3
1 2
3 4
5 6

输出

32

提示

用一个结构体表示卡片,按 b 从大到小排序,枚举每张牌作为 b 最小的,那最好的结果一定是前头到这里所有牌都取,伤害值为从前头到这里所有 a 的和乘上这个 b ,取以每张牌作为 b 最小的时候的最大伤害值的最大值。