Problem4645--卡牌游戏 IV

4645: 卡牌游戏 IV

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

老周君在玩一种卡牌游戏,他有nnn张卡牌,每张卡牌上写着两个正整数 $a_i, b_i$,$a_i$ 表示这张卡牌的能量值,$b_i$ 表示这张卡牌的魔法值。
他准备一张一张打出这 $n$ 张卡牌,每张卡牌会对敌人造成的伤害是这张卡牌的能量值乘魔法值。
但是老周觉得这样把这 $n$ 张卡牌都出完对敌人造成的伤害之和还是不够大,所以他偷偷学会了一种仙术。
老周施展一次仙术的时候会任意选择两张卡牌,把它们的魔法值交换,能量值不交换。
他可以使用任意次仙术,当然也可以一次都不使用,他想知道使用了若干次仙术以后一张一张打出这 $n$ 张卡牌,对敌人造成的伤害之和最大是多少。

Input

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

Output

输出一行,包含一个整数,表示使用若干次仙术以后一张一张打出卡牌,对敌人造成的伤害之和的最大值。

Sample 1 Input

3
1 6
3 4
5 2

Sample 1 Output

44

Source/Category