100 #P1175. *【单调队列：二维DP】猴子吃香蕉[GDKOI2007改编]
*【单调队列：二维DP】猴子吃香蕉[GDKOI2007改编]
Description
【题意】一个猴子要吃香蕉，一共N棵香蕉树排列在一条直线上，它一开始在第一棵树上。
每棵树上有不同数量的香蕉，猴子每次最多的跳跃距离为D，而且最多只能跳M次，问猴子最多能吃到多少香蕉？
【输入格式】
第一行 三个整数 N,D,M (M<N<=5000，D<=10000)；
下面N行 每行两个整数 ai,bi (ai,bi<=1000000，ai为正整数) 分别表示每棵树上的香蕉数目，以及每棵树的位置(树的位置是递增的）。
数据保证没有两棵香蕉树在同一位置，以及b[1]=0。
【输出格式】
一个整数，表示猴子最多吃到的香蕉数。
【样例输入】
5 5 2
6 0
8 3
4 5
6 7
9 10
【样例输出】
20
来源GDKOI2007 改编