DongDong跳一跳
题号:NC23804
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

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

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

输入描述:

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

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

数据范围:1<=n<=200000,1<=m<=500,对于每根柱子的x,y,1<=x<=1000000,1<=y<=1000000

输出描述:

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

输入

复制
4 4
1 0
2 100
100 5
6 10

输出

复制
110