Home => ProblemSet => 300-10:机器人
Problem1416--300-10:机器人

1416: 300-10:机器人

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

一个机器人在数轴上移动,机器人所在的坐标始终为整数(可以是负数,零,或正数)。假设机器人当前在数轴上 x 点,当收到指令 (d,k) 后(其中 d 是整数,k 是正整数),机器人会移动到数轴上 (x+d) 点的位置,并获得 |2kx+kd| 的分数(其中| |表示绝对值)。

机器人初始时在数轴上的 0 点。现在给定了 n 个指令 (d1,k1),(d2,k2),...,(dn,kn),机器人需要执行其中每一个指令恰好一次,但是执行指令的先后次序还没有确定。请你合理安排执行这些指令的顺序,使得机器人获得的总分数最大化。你只需要输出最大总分即可。

Input

第一行一个正整数 n,表示指令的数量。
接下来 n 行每行两个整数 di,ki。

Output

输出一个非负整数,表示最大总分。

Sample Input Copy

3
-3 2
0 1
3 2

Sample Output Copy

18

HINT

Source/Category