这是一个炎热的夏日。
懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置,以便可以在短距离内尽可能多地吃到美味的草。
贝茜所在的田野中共有 N 片草地,我们可以将田野视作一个一维数轴。
第 i 片草地中包含 gi 单位的青草,位置坐标为 xi。
不同草地的位置不同。
贝茜想选取田野中的某个点作为她的初始位置(可能是某片草地所在的点)。
只有一片草地与她的初始位置的距离不超过 K 时,贝茜才能吃到那片草地上的草。
如果贝茜选择最佳初始位置,请确定她可以吃到的青草最大数量。
第一行包含两个整数 N 和 K。
接下来 N 行,每行描述一片草地,包含两个整数 gi 和 xi。
输出如果贝茜选择最佳初始位置,则她可以吃到的青草最大数量。
输入样例:
4 3 4 7 10 15 2 2 5 1
输出样例:
11
样例解释: 最佳初始位置选择为 x=4,可以吃到 x=1,x=2,x=7 处的青草。
1≤N≤10^5 ,
1≤gi≤10000,
0≤xi≤10^6,
1≤K≤2×10^6