金库的终结
Background
在强盗的一番破坏后,只剩下了几个房间有金币,在取完最后一次金币后。这个金库就废弃了
金库,承载着一代一代人的记忆,从我们的记忆里飘走,飘走......
Description
现在房间不是连续的了 ,也就是说 ,题目中没有提及的房间金币数都是0
当你取走房间 \(x\) 里的金币后,从 \(x-b\) 到 \(x+b\) 的房间都会被摧毁
依然求出最多能取出多少个金币。
Format
Input
第一行一个整数 \(n\) 和 \(b\) .
接下来 \(n\) 行,每行两个整数,\(p\) 和 \(v\) 表示房间的位置,房间所剩金币数
保证 \(p_i\) 各不相同
Output
最多能有多少金币
Sample 1
Input
4 1
1 2
2 1
4 7
5 5
Output
9
选择位于 1
和 4
的房间
Limitation
对于 \(28\%\) 的数据
\( 1 \le n \le 10 \)
对于另外 \(14\%\) 的数据
\(p_i=i\)
对于另外 \(14\%\) 的数据
\( b=1 \)
对于100% 的数据
\( 1 \le n \le 5 \times 10^6\)
\( 1 \le p_i \le 2 \times 10^8 \)
\( 1 \le v_i \le 10^9 \)
\( p_{i-1} < p_i \)
Source
信息
- ID
- 1006
- 难度
- 2000
- 分类
- (无)
- 标签
- 递交数
- 4
- 已通过
- 2
- 通过率
- 50%
- 上传者