(这道题和上一题题面一样，只是数据范围增加了)

题目描述

贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 2000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。 每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

输入格式

* 第1行一个整数N

* 第2行到第N行: 每行2个整数 x(i)和 p(i), 数据范围是0到500,000.

输出格式

* 一个整数表示贝西的最大可能得分。

样例 #1

样例输入 #1

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

样例输出 #1

25