题目描述

一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i, y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围（那个边长为 $m$ 的正方形）的边必须与 $x$ 轴、$y$ 轴平行。

若目标位于爆破正方形的边上，该目标不会被摧毁。

现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。

可能存在多个目标在同一位置上的情况。

输入格式

输入的第一行为整数 $n$ 和整数 $m$；

接下来的 $n$ 行，每行有 $3$ 个整数 $x, y, v$，表示一个目标的坐标与价值。

输出格式

输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 $32767$）。

数据范围

对于 $100\%$ 的数据，保证 $1 \le n \le 10^4$，$0 \le x_i, y_i \le 5\times 10^3$，$1 \le m \le 5\times 10^3$，$1 \le v_i < 100$。

样例

输入样例 1

2 1
0 0 1
1 1 1

输出样例 1

1

提示

边长 $1$ 的正方形只能覆盖 $1\times1$ 的格点区域，因此同时覆盖 $(0,0)$ 与 $(1,1)$ 是不可能的，答案是 $1$。

做法：把目标放到 $(x+1, y+1)$ 上做二维前缀和，然后枚举正方形的左上角，$O(1)$ 求出正方形内的价值和，总复杂度 $O(\text{坐标范围}^2)$。