USACO2014MAR，铜组第二题

题目描述

在炎热的夏日，贝茜（Bessie）这头牛犯懒了。她想在自己的牧场里找一个位置，使得在距离该位置不超过 ( K ) 步的范围内，能吃到尽可能多的美味青草。

牧场里有 ( N ) 丛青草（( 1 <= N <= 100,000 ) ），可以看作分布在一条一维数轴上。第 ( i ) 丛青草的位置是 ( x_i )（( 0 <= x_i <= 1,000,000 ) ），包含 ( g_i ) 单位的青草（( 1 <= g_i <= 10,000 ) ）。贝茜要选一个初始位置（可以是某丛青草的位置 ），使得在该位置距离 ( K ) 步范围内（即区间 ([pos - K, pos + K]) ）的青草总量最大。

请帮助贝茜计算，选择最优初始位置时，能吃到的最大青草总量。

输入格式

• 第 1 行：两个整数 ( N )（青草丛数 ）和 ( K )（最大距离 ）。
• 第 2 至 ( N+1 ) 行：每行两个整数 ( g_i ) 和 ( x_i )，描述第 ( i ) 丛青草的青草量和位置。

样例输入

4 3
4 7
10 15
2 2
5 1

输入解析：

• 4 丛青草，最大距离 ( K=3 )。
• 各丛青草的位置和青草量：(7,4)、(15,10)、(2,2)、(1,5)（注意输入顺序是 g_i x_i ，即第一丛是位置 7 有 4 单位，第二丛位置 15 有 10 单位，依此类推 ）。

输出格式

输出一行，为贝茜选择最优初始位置时，距离 ( K ) 步范围内能吃到的最大青草总量。

样例输出

11

输出解析：
最优位置是 ( x=4 )，此时距离 3 步范围内（区间 ([1,7]) ）包含：

• 位置 1（青草量 5 ）、位置 2（青草量 2 ）、位置 7（青草量 4 ）。
  总青草量 ( 5 + 2 + 4 = 11 )。