题目背景

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$ 行：输出一个整数，表示最大收益。

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

-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$。