B21 习题-5 激光炸弹

题目描述

兔子国最近新研发了一种激光炸弹，可以摧毁边长为 $R$ 的正方形内的所有的打击目标。

待打击区域可以看成一个平面坐标系，图上有 $n$ 个目标，$x_i,y_i$ 表示目标的坐标， $v_i$ 表示该目标的重要度。激光炸弹能摧毁以$(x_a,y_a)$为左上角，$(x_{a+R-1},y_{a+R-1})$为右下角组成的正方形内的所有目标（正方形必须与$x,y$ 轴平行，且位于正方形边界上的目标不会被摧毁）。

请你找到一种投弹方式，使得这枚激光炸弹能摧毁目标区域的重要度之和最大。

输入格式

第一行两个整数 $n,R$ 表示图上的目标个数与激光炸弹的打击边长；

接下来的 $n$ 行每行三个正整数 $x_i,y_i,v_i$ ，表示第 $i$ 个目标的位置及重要度。

输出格式

一行一个正整数，表示能摧毁的最大重要度之和。

样例输入

2 1
0 0 1
1 1 1

样例输出

1

数据范围

对于 $100\%$ 的数据： $1 \le n\le 10^4$，$0\le x_i,y_i,v_i \le 5000$ 。