TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3412
  • Problem
  • P3412【Codeforces #312 div2 A】Lala Land and Apple Trees
    Limits : Time Limit : 10000 MS   Memory Limit : 262144 KB
    Judgment Tips : 1s,256MB
    Description

    Amr在Lala Land摘苹果。
    有n棵苹果树,第i棵坐标为xi,树上有ai个苹果。
    Amr摘苹果的方式很奇特。Amr一开始站在坐标为0的位置,可以选择向左或者向右走。当他遇到这个方向上第一棵还没有被摘过的苹果树时,他会爬到树上去把上面的苹果都摘下来,然后沿着与刚才相反的方向前进。如果这个方向上没有苹果树或者这些苹果树都被摘过了,它就会停下来开始吃苹果。
    Amr想吃尽量多的苹果,那么,Amr最多可以吃到多少苹果呢?

    Input Format

    第一行一个整数n,表示苹果树的数量。
    接下来n行,每行有两个整数xi,ai,表示第i棵苹果数的坐标和苹果数量。坐标互不重复,没有坐标为0的苹果树。

    Output Format

    输出一个整数,表示Amr最多可以吃多少个苹果。

    Sample Input

    样例输入1:
    2
    -1 5
    1 5

    样例输出2:
    3
    -2 2
    1 4
    -1 3

    样例输入3:
    3
    1 9
    3 5
    7 10

    Sample Output

    样例输出1:
    10

    样例输出2:
    9

    样例输出3:
    9

    Hint

    样例解释:
    第一组,不管一开始向左还是向右都可以把所有苹果吃完。
    第二组,先向左,摘下x=-1那棵树的苹果,再向右,摘下x=1那棵树的苹果,再向左,摘下x=-2那棵树的苹果。
    第三组,先向右,摘下x=1那棵树的苹果,这时左边已经没有树了,就停止摘苹果。

    数据范围:
    1<=n<=100
    -105<=xi<=105
    1<=ai<=105