#P1047. 放牛
放牛
题目描述
面条老师牵着牛在草原上放牧,但懒惰的面条老师希望将牛绳系在草原上的某个位置,让牛自己去吃草。
草原上共有片草地,我们可以将草原视作一个一维数轴。
第片草地中包含单位的青草,位置坐标为。
面条老师想要选取草原中的某个点作为系牛绳的位置。
牛绳长度为,也就是说只有当一片草地与系牛绳的位置距离不超过的时候,牛才能吃到那片草地上的草。
下面请你帮助面条老师选出最佳系牛绳的位置,计算出牛最多能吃多少单位的草。
输入格式
输入包括若干行。
第一行包含两个整数 ,代表草地的数量和牛绳的长度。
接下来行,每行包含两个整数,分别代表第i块草地青草的数量和位置坐标。
输出格式
输出包括一行,为牛最多能吃到的青草。
样例 #1
样例输入 #1
4 3
4 7
10 15
2 2
5 1
样例输出 #1
11
样例 #2
样例输入 #2
5 3
4 2
3 3
3 6
2 4
4 7
样例输出 #2
16
说明/提示
【样例解释 #1】
最佳系牛绳的位置是,可以吃到处的青草。
【样例解释 #2】
最佳系牛绳的位置是,可以吃到所有的青草。
【数据范围】
;
;
;
。