Alldream Monthly 2019.4

D. DongDong跳一跳
PDF 题面可用
你可以在这里下载。

单点时限: 1.0 sec

内存限制: 512 MB

DongDong有一只超可爱的英短喜欢跳一跳,但此跳一跳非彼跳一跳

有$n$根柱子,每根柱子都有一个高度和柱子上面鱼干的数量,英短开始的时候可以选择站在任意一根柱子上,每次跳跃不限长度而且只能从左向右跳跃,但只能跳到高度与当前所站高度差绝对值小于等于$m$的柱子上,英短可贪心了,想吃最多的鱼干,请你设计一个程序能让英短吃到最多的鱼干(最终不一定要落在第$n$根柱子上)。

输入格式

第一行给定两个整数$n$,$m$

接下来$n$行,每行$x$,$y$表示这根柱子高度为$x$,上面有$y$根鱼干

输出格式

输出英短最多可以吃到多少鱼干

样例

Input
4 4
1 0
2 100
100 5
6 10
Output
110

提示

  • 30pts: $n \leq 5000$
  • 100pts:$1 \leq n \leq 200000, 1 \leq m \leq 500$
  • 对于每根柱子的$x,y$, $1 \leq x \leq 1000000,1 \leq y \leq 1000000$