[JSOI2009] 火星藏宝图

题目背景

JSOI2009第三轮二试

题目描述

在火星游玩多日,jyy 偶然地发现了一张藏宝图。根据藏宝图上说法,宝藏被埋藏在一个巨大的湖里的 $N$ 个岛上 $(2\le N \le 2 \times 10^{5})$。为了方便描述,地图把整个湖划分成 $M$ 行 $M$ 列 $(1\le M\le 1000)$,共 $M \times M$ 个小块,并把所有岛按照 $1...N$ 编了号。第 $i$ 个岛位于第 $X_i$ 行 $Y_i$ 列 (设其坐标为 $(X_i,Y_i)$的格子 ( $X_i,Y_i$ 均为整数,并且满足 $1<=X_i,Y_i<=M$ ),岛上藏有价值财富 $V_i(1\le V_i\le 10,000)$。湖的左上角 $(1,1)$ 和右下角 $(M,M)$ 都有岛,有桥将它们与陆地相连。 jyy 没费多大劲,就找到了那个湖,同时哭笑不得地发现,所谓的财富,是各个岛上出产的珍稀水果。jyy 在左上角的岛的岸边找到了一条小木船,他可以划船到其他岛上去。划船是要消耗体力的,具体地说,等于两岛 Euclidean 距离的平方(即,从 $(X_1,Y_1)$ 划船到 $(X_2,Y_2)$ 所耗费的体力为 $(X_1-X_2)^2+(Y_1-Y_2)^2$ 个单位)。jyy 可以吃水果来恢复体力,吃掉 $1$ 单位价值的水果能恢复 $1$ 单位体力。 现在 jyy 打算从 $(1,1)$ 旅行到 $(M,M)$,沿途收集珍稀水果。按藏宝图上的提示,jyy 离开一个岛后,就只能去该岛右下方的区域(正下和正右方向也是允许的),否则会遭遇水怪。jyy 可以在旅行途中饿一段时间,即体力为负。但抵达终点后,只要身边有足够多的水果,他就会通过吃水果将体力恢复到旅行前的水平。 jyy想知道,经过一次旅行,他最多能得到多少收益,即 `jyy 收集到的水果总价值- jyy 在旅途中花的总体力` 。(如果吃完所有水果他还饿着,收益就是负数,具体的例子见样例)

输入输出格式

输入格式


第 $1$ 行:两个整数 $N,M$。第 $2...N+1$ 行:每行 $3$ 个整数,第 $i+1$ 行的 $3$ 个整数分别为 $ X_i$,$Y_i$,$V_i$。每个岛的坐标不同。保证存在坐标 $(1,1)$ 和 $(M,M)$ 的岛。

输出格式


第 $1$ 行:输出一个整数,表示最大收益。

输入输出样例

输入样例 #1

4  10 
1  1  20 
10 10 10 
3  5  60 
5  3  30

输出样例 #1

-4

说明

### 样例解释 $20+60+10-\left ( \left(3-1 \right )^2+\left (5-1 \right )^2 \right )-\left ( \left (10-3 \right )^2+\left (10-5 \right )^2 \right )=-4$ ### 数据范围 对 $20\%$ 的数据 $M\le 200$,且 $N\le 2\times 10^3$。 对 $50\%$ 的数据 $M\le 200$,且 $N\le 2\times 10^4$。 对 $100\%$ 的数据 $M\le 1000$,且 $N\le 2\times 10^5$。