中文
日本語
English
| P3412【Codeforces #312 div2 A】Lala Land and Apple Trees | ||
|
問題説明
Amr在Lala Land摘苹果。
有n棵苹果树，第i棵坐标为xi，树上有ai个苹果。
Amr摘苹果的方式很奇特。Amr一开始站在坐标为0的位置，可以选择向左或者向右走。当他遇到这个方向上第一棵还没有被摘过的苹果树时，他会爬到树上去把上面的苹果都摘下来，然后沿着与刚才相反的方向前进。如果这个方向上没有苹果树或者这些苹果树都被摘过了，它就会停下来开始吃苹果。
Amr想吃尽量多的苹果，那么，Amr最多可以吃到多少苹果呢？
入力形式
第一行一个整数n，表示苹果树的数量。
接下来n行，每行有两个整数xi,ai，表示第i棵苹果数的坐标和苹果数量。坐标互不重复，没有坐标为0的苹果树。
出力形式
输出一个整数，表示Amr最多可以吃多少个苹果。
サンプル入力
样例输入1：
2
-1 5
1 5
样例输出2：
3
-2 2
1 4
-1 3
样例输入3：
3
1 9
3 5
7 10
サンプル出力
样例输出1：
10
样例输出2：
9
样例输出3：
9
ヒント
样例解释：
第一组，不管一开始向左还是向右都可以把所有苹果吃完。
第二组，先向左，摘下x=-1那棵树的苹果，再向右，摘下x=1那棵树的苹果，再向左，摘下x=-2那棵树的苹果。
第三组，先向右，摘下x=1那棵树的苹果，这时左边已经没有树了，就停止摘苹果。
数据范围：
1<=n<=100
-105<=xi<=105
1<=ai<=105