C1209 [JSOI2009]火星藏宝图

在火星游玩多日，jyy 偶然地发现了一张藏宝图。根据藏宝图上说法，宝藏被埋藏在一个巨大的湖里的 $N$ 个岛上 $(2 \le N \le 200,000)$。为了方便描述，地图把整个湖划分成 $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 \le X_i,Y_i \le 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

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

样例输出 1

-4