1429: #6217. 扑克牌

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定一摞 nnn 张扑克牌,每张牌上有两个值 ai,bia_i,b_iai,bi, 有以下两种操作:

1,对于牌顶的牌 (atop,btop)(a_{top}, b_{top})(atop,btop) , 从上到下将把包括他在内的 atopa_{top}atop 张牌扔掉并获得 btopb_{top}btop的愉悦度。注意:如果牌堆里面没有 atopa_{top}atop 张牌的话不能进行此操作。

2,把牌堆顶的牌扔到这摞牌的最下面。

现在你可以进行无限次操作,也可以在任意时刻停下来,问你最多能获得多少愉悦度

输入格式

第一行一个数字 nnn, 接下来 nnn 行从上到下描述每张牌:每行两个数字表示牌上两个数字 ai,bia_i,b_iai,bi

输出格式

一行一个数,表示最多的愉悦值。

样例

样例输入

3 
2 3
1 2
1 1

样例输出

5

样例解释

先选择第二张牌,然后再一次轮到第一张牌的时候选择第一张牌,然后没有牌了停下来,共获得了 2+3=52+3=52+3=5 的 愉悦度

数据范围与提示

对于30%30\%30%的数据,有 n≤5n \le 5n5

对于100%100\%100%的数据,有 n≤103,ai≤n,bi≤103n \le 10^3, a_i \le n, b_i \le 10^3n103,ain,bi103