题目描述
新的机关需要解决的问题也是跳房子问题。但是和前面小帅想到的问题有点区别。
烛龙战队首先在地面确定一个起点，然后在起点右侧画n个格子，这些格子都在同一条直线上。第i个格子到起点的距离为dis[i]，每个格子内有一个数字a[i]，表示到达这个格子能得到的分数。
玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
这里的机器人的默认弹跳距离为d、灵活度为0，可以使用金币来增加灵活度，每使用一个金币，灵活度就会加1。现在想要得到k分，问最少需要花多少金币。
输入
第一行三个正整数n，d，k，分别表示格子的数目，默认弹跳距离，以及想要获得的分数，相邻两个数之间用一个空格隔开。(1 <= n,d,k <= 2000)
接下来n行，每行两个正整数xi,si，分别表示起点到第i个格子的距离以及第i个格子的分数。(1 <= xi <= 10^9,1 <= si <= 100000)
两个数之间用一个空格隔开，保证xi按递增顺序输入。
输出
共一行，一个整数，表示可以获得的最高分。
样例输入
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2样例输出
2