2044. LLL吃葡萄

时间限制 1000 ms   内存限制 256 MB

LLL很喜欢吃葡萄!

这天,LLL来到了一个葡萄庄园,她很高兴,因为这里到处都是她喜欢吃的葡萄。

可是LLL经过一段疲惫的旅途之后已经不愿意再多走一步路,她只想找一个地方坐下然后尽情地开始吃葡萄。LLL的胳膊长度有限,只能摘到在她胳膊长度之内的葡萄,同时她又希望能吃到的葡萄越多越好。

假设整个葡萄庄园的葡萄藤都在一条直线上,每串葡萄都有它的位置$x_i$和葡萄颗数$a_i$,注意同一个位置可能有多串葡萄,LLL胳膊能碰到的范围为$m$,表示她能摘到坐标在$[j,j+m-1] $ $(1≤j≤j+m-1≤10^9)$之间的葡萄。

LLL坐车来到葡萄庄园,她可以让司机把车停在庄园里的任意位置(坐车是不会累的!),但下车之后她就不愿意再移动位置。葡萄庄园实在是太大了,LLL不知道她应该停在哪里才能吃到最多的葡萄,但她现在只关心她最多能吃到多少葡萄,请你帮忙算出她最多能吃到的葡萄个数。

输入数据

输入第一行包含两个整数$n$,$m$,表示葡萄串的数量和LLL的接触范围,$1≤n≤10^5$,$1≤m≤10^5$。

接下来$n$行,其中第$i$行包括两个整数$x_i$和$a_i$,分别表示第$i$串葡萄的位置坐标和葡萄颗数,$1≤ x_i ≤10^9$,$1≤ a_i ≤100$。

输出数据

输出一个整数,表示LLL最多能吃到的葡萄个数。

样例输入

复制
5 2
3 5
3 3
4 4
5 6
6 3 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
12  \n

样例说明

接触范围为2,因此可以选择坐标为3~4、4~5或者5~6的葡萄串。

选择坐标为3的两串葡萄(葡萄颗数分别为5和3)和坐标为4的一串葡萄(葡萄颗数为4)能吃到的葡萄颗数最多为12。

提交

请先 登录

© 2024 FAQs Contact About