题目描述

又是一个炎热的夏天，Bessie 感觉差不多要热疯了，它想找一段茂盛的草场避暑。牧场里面有 $N$（$1 \le N \le 10^5$）个点有茂盛的草场，其它的点没有牧草，所有点都在同一条坐标直线上。这 $N$ 个点都有两个数据：分别表示这个点的牧草的茂盛程度 $g_i$（$1 \le g_i \le 10^4$）和坐标 $x_i$（$0 \le x_i \le 10^6$）。Bessie 想找到一个点（不一定是有牧草的点）避暑，使得这个点的前后长度均为 $K$（$1 \le K \le 2 \times 10^6$）的范围内（即坐标区间 $[x-K, x+K]$）所有草场的茂盛程度之和最大。你能帮助它找到这个最大值吗？

输入格式

第一行包含两个整数 $N$ 和 $K$。
接下来 $N$ 行，每行包含两个整数 $g_i$ 和 $x_i$，分别表示第 $i$ 个草场的茂盛程度和位置。

输出格式

输出一个整数，表示茂盛程度之和的最大值。

样例

4 3
4 7
3 1
4 2
5 10

11

样例解释

Bessie 选择在坐标 $x=4$ 处避暑，此时前后各 $3$ 单位长度的区间为 $[1, 7]$。该区间内包含三个草场：位置 $1$（茂盛程度 $3$）、位置 $2$（茂盛程度 $4$）和位置 $7$（茂盛程度 $4$），茂盛程度之和为 $3+4+4=11$，这是能达到的最大值。

数据范围

• $1 \le N \le 10^5$
• $1 \le g_i \le 10^4$
• $0 \le x_i \le 10^6$
• $1 \le K \le 2 \times 10^6$