题目描述

给定一摞 $n$ 张扑克牌，每张牌上有两个值 $(a_i, b_i)$，有以下两种操作：

1. 对于牌堆顶的牌（记为第 $top$ 张，即当前牌堆最上方的牌），从上到下把包括它在内的 $a_{top}$ 张牌扔掉并获得 $b_{top}$ 的愉悦值。注意：如果牌堆里面没有 $a_{top}$ 张牌的话不能进行此操作。
2. 把牌堆顶的牌扔到这摞牌的最下面。

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

输入格式

第一行一个数字 $n$，接下来 $n$ 行从上到下描述每张牌，每行两个数字表示牌上两个数字 $(a_i, b_i)$。

输出格式

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

样例

样例输入

3
2 3
1 2
1 1

样例输出

5

数据范围与提示

• 对于 30% 的数据，有 $n \leq 5$。
• 对于 100% 的数据，有 $n \leq 10^5$，$a_i \leq n$，$b_i \leq 10^3$。