第32618题 程序题
跳跃的小猫:跳柱子获取最多鱼干

法玛尔·约翰除了他的牛以外还有一只超可爱的英短喜欢跳一跳,但此跳一跳非彼跳一跳。

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

输入描述

第一行给定两个整数n,m 接下来n行,每行x,y表示这根柱子高度为x,上面有y根鱼干

输出描述

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

输入样例1

4 4
1 0
2 100
100 5
6 10

输出样例1

110

提示

样例解释

从高度为2的柱子跳到高度为6的柱子,高度差绝对值为4≤m=4,可行,获得鱼干100+10=110。

数据规模与约定

  • 对于30%的数据: n≤5000
  • 对于100%的数据:1≤n≤200000, 1≤m≤500
  • 对于每根柱子的x,y:1≤x≤1000000, 0≤y≤1000000
编辑模式
程序运行统计
暂无判题统计