问题 D: 跳飞机

问题 D: 跳飞机

时间限制: 1 Sec  内存限制: 256 MB
提交: 72  解决: 34
[提交][状态][讨论版][命题人:]

题目描述

跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。


游戏规则如下:

在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。

每个格子内有一个数字(整数),表示到达这个格子能得到的分数。

玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。

第二次再从当前位置继续向右跳,依此类推。

规则规定:玩家每次都必须跳到当前位置右侧的一个格子内。

玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。

现在小 R研发了一款弹跳机器人来参加这个游戏。

但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能在一个范围之内,也就是它最近至少要跳L米,最远能跳R米,(1<=L<=R<=10^9)。也就是机器能跳L,L+1,L+2,.....R。请问这个机器人最多能拿到多少分数。




输入

第一行三个正整数 n,L,R分别表示格子的数目,机器人跳的最短距离,机器人跳的最长距离,相邻两个数之间用一个空格隔开。

接下来 n行,每行两个正整数 xi,si,分别表示起点到第 i个格子的距离以及第 i个格子的分数。两个数之间用一个空格隔开,保证 xi按递增顺序输入。

输出

共一行,一个整数,表示机器人能得到的最大分数

样例输入

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出

9

提示






1≤n≤500000,



1≤xi,L,R≤10^9



|si|≤10^5










[提交][状态]