题目描述

FJ 给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。

为了训练贝西更好地控制跳跃，FJ 在农场的一条笔直一维路径上设置了一个练习场。他在路径的不同位置放置了 $N$ 个目标点 $(1 \le N \le 1000)$，贝西需要尝试落在这些点上。目标点 $i$ 的位置坐标为 $x_i$，如果贝西落在上面，就能获得 $p_i$ 分。

贝西可以从任意一个目标点开始起跳，并且只能朝一个方向移动（向左或向右），从一个目标点跳到另一个目标点。每次跳跃的距离必须大于等于上一次跳跃的距离，而且必须落在目标点上。

每跳到一个目标点，贝西可以拿到该点的得分。请计算他的最大可能得分。

输入格式

• 第一行，一个整数 $N$。

• 第二行到第 $N+1$ 行，第 $i+1$ 行包含两个整数 $x_i$ 和 $p_i$，其中 $0 \le x_i, p_i \le 10^6$。

输出格式

• 一行一个整数，表示贝西的最大得分。

6 
5 6 
1 1 
10 5 
7 6 
4 8 
8 10 

25 

提示

有 $6$ 个目标点。第一个目标点位于位置 $x=5$，价值 $6$ 分，依此类推。

贝西从位置 $x=4$（$8$ 分）跳到位置 $x=5$（$6$ 分），再跳到位置 $x=7$（$6$ 分），最后跳到位置 $x=10$（$5$ 分）。共计 $25$ 分。

数据规模与约定

• $1 \le N \le 1000$
• $0 \le x_i, p_i \le 10^6$