← 返回题目列表

Codeforces · 558/A

A. 拉拉土地和苹果树

中文机器翻译题面 查看原题

Amr 住在 Lala Land。 Lala Land是一个非常美丽的国家,位于坐标线上。拉拉乐园因到处长满苹果树而闻名。

拉拉乐园正好有 n 棵苹果树。 i 号树位于 xi 位置,上面长有 ai 个苹果。阿穆尔想从苹果树上采集苹果。 Amr 目前处于 x = 0 的位置。一开始,他可以选择向右走还是向左走。他将继续朝他的方向走,直到遇到一棵他以前没有去过的苹果树。他会拿走所有的苹果,然后调转方向,继续朝这个方向走,直到遇到另一棵他以前没有去过的苹果树,依此类推。换句话说,阿姆鲁在访问每棵新苹果树时都会改变方向。当他面对的方向上不再有他没有去过的树时,Amr 将停止收集苹果。

他最多可以收集多少个苹果?

输入

第一行包含一个数字n (1 ≤ n ≤ 100),即拉拉乐园里苹果树的数量。

接下来的 n 行包含两个整数 xi, ai ( - 105 ≤ xi ≤ 105, xi ≠ 0, 1 ≤ ai ≤ 105),代表第 i 棵树的位置和上面苹果的数量。

保证每个坐标最多有一棵苹果树。保证在 0 点没有树生长。

输出

输出 Amr 可以收集的最大苹果数量。

示例

输入 #1

2
-1 5
1 5

输出 #1

10

输入 #2

3
-2 2
1 4
-1 3

输出 #2

9

输入 #3

3
1 9
3 5
7 10

输出 #3

9

注意

在第一个样本测试中,Amr 一开始选择向左还是向右并不重要。在这两种情况下,他都会得到所有的苹果。

在第二个示例测试中,最佳解决方案是向左走到 x = - 1,从那里收集苹果,然后方向将反转,Amr 必须走到 x = 1,从那里收集苹果,然后方向将反转,Amr 前往最终的树 x = - 2。

在第三个样本测试中,最佳解决方案是向右移动到 x = 1,从那里收集苹果,然后方向将反转,Amr 将无法再收集苹果,因为他的左边没有苹果树。