问题1184--捕鱼

1184: 捕鱼

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

由于桥牌实在是太难了,Miaoyao又投向了一个古老的游戏--捕鱼达人。但他的游戏技术实在不好,于是希望你能帮他编写一个程序来计算出最优的游戏策略。
在这个游戏中,你需要发射一个渔网来捕获鱼,但同时也可能捞到石头。当前的画面中有n件物品,每件物品可能为鱼或者石头,第i件物品可以视为无限大二维平面上的一个整点(xi,yi),捕获它可以获得相应的得分wi(若的得分小于0则表示该物品为石头,捞上来会扣分)。渔网可以视为一个边长为R的正方形,必须平行于坐标轴放置,顶点可以位于二维平面内的任意整点。放置渔网后,在其内部及边界上的物品均会被捕捞。Miaoyao想知道他当前释放一张渔网所能获得的最大得分是多少。特别地,如果任何撒网策略都不够好,他可以选择不释放渔网。



输入

第一行两个整数n和R,表示物品的数量与渔网的边长。

接下来n行,第i行包含三个整数xi,yi,wi,表示一件物品的坐标与分值。保证不会有两件物品处于同一个位置。

输出

一个整数,表示Miaoyao的最大得分。

样例输入 Copy

5 3
0 0 10
-1 0 -5
0 3 2
1 0 -1
3 3 -3

样例输出 Copy

9

提示

1<=n<=200000

1<=R<=1000

-1000<=xi,yi<=1000

-10000<=wi<=10000


样例解释:其中一种可行的策略是让渔网的左上角处于(0,0),右上角处于(3,0),左下角处于(0,-3),右下角处于(3,-3)

来源/分类