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最多能吃到的葡萄个数。
接触范围为2,因此可以选择坐标为3~4、4~5或者5~6的葡萄串。
选择坐标为3的两串葡萄(葡萄颗数分别为5和3)和坐标为4的一串葡萄(葡萄颗数为4)能吃到的葡萄颗数最多为12。