当前没有测试数据。

题目描述

河面上有一排石墩，编号从 $1$ 到 $N$，第 $i$ 个石墩距离左岸的距离为 $D_i$，高度为 $H_i$。初始时你在左岸，想要过河到右岸。

你可以从左岸跳到任意一个石墩上，也可以从任意一个石墩跳到右岸。从一个石墩跳到另一个石墩时，只能跳到距离更远且高度不低于当前石墩的石墩上。从一个石墩跳到另一个石墩或者从石墩跳到右岸，可以得到两个石墩高度之和（从左岸出发或到达右岸时，高度视为 $0$）。

请你计算，从左岸出发，最终到达右岸，能够获得的最大得分是多少？

输入格式

第一行输入一个整数 $N$，表示石墩数量。

接下来 $N$ 行，每行输入两个整数 $D_i$ 和 $H_i$，表示第 $i$ 个石墩的距离和高度。

输出格式

输出一个整数，表示最大得分。

样例 #1

输入

5
1 3
2 5
3 4
4 6
5 2

输出

30

样例 #2

输入

6
1 5
2 3
3 7
4 2
5 8
6 4

输出

38

样例说明

样例 1 解释

石墩按距离排序后，高度分别为 $[3, 5, 4, 6, 2]$。

最优路径：左岸 → 石墩2(高度5) → 石墩4(高度6) → 右岸

得分：$0+5 + 5+6 + 6+0 = 5 + 11 + 6 = 22$... 实际上需要重新计算。

最优解可能是：左岸 → 石墩1(高度3) → 石墩2(高度5) → 石墩4(高度6) → 右岸

得分：$0+3 + 3+5 + 5+6 + 6+0 = 3+8+11+6 = 28$

或者直接：左岸 → 石墩4(高度6) → 右岸，得分：$0+6 + 6+0 = 12$

数据范围

对于 $30\%$ 的数据，$1 \le N \le 100$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le D_i, H_i \le 10^9$，石墩按距离从小到大给出。