P4056 [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

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

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

### 样例解释 $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$。