Description

After traveling on Mars for many days, jyy accidentally discovered a treasure map. According to the map, the treasure is buried on $N$ islands $(2\le N \le 2 \times 10^{5})$ in a huge lake. For convenience, the map divides the entire lake into $M$ rows and $M$ columns $(1\le M\le 1000)$, a total of $M \times M$ cells, and numbers all islands from $1$ to $N$. The $i$-th island is located at row $X_i$, column $Y_i$ (that is, on the cell with coordinates $(X_i,Y_i)$, where $X_i,Y_i$ are integers satisfying $1<=X_i,Y_i<=M$), and the island contains treasure worth $V_i(1\le V_i\le 10,000)$. There are islands at the top-left $(1,1)$ and bottom-right $(M,M)$ corners of the lake, and there are bridges connecting them to the land.

jyy soon found the lake and, to his amusement, discovered that the so-called treasure is the rare fruits produced on each island. At the shore of the island at the top-left corner, jyy found a small wooden boat, with which he can row to other islands. Rowing consumes stamina equal to the square of the Euclidean distance between two islands (that is, rowing from $(X_1,Y_1)$ to $(X_2,Y_2)$ costs $(X_1-X_2)^2+(Y_1-Y_2)^2$ units of stamina). jyy can eat fruit to restore stamina; consuming 1 unit of fruit value restores 1 unit of stamina.

Now jyy plans to travel from $(1,1)$ to $(M,M)$, collecting rare fruits along the way. As hinted on the treasure map, after leaving an island, he may only go to the region to its lower-right (moving directly down or directly right is also allowed); otherwise, he will encounter a water monster. jyy may travel while hungry, i.e., stamina can be negative. Upon reaching the destination, as long as he has enough fruit with him, he will eat to restore his stamina to the pre-trip level.

jyy wants to know, after one trip, what is the maximum net gain, defined as jyy’s total collected fruit value minus jyy’s total stamina spent during the trip. (If he is still hungry after eating all the fruit, the net gain is negative; see the sample for a specific example.)

Input Format

The first line contains two integers $N,M$.
Lines $2$ to $N+1$: each line contains $3$ integers. On line $i+1$, the $3$ integers are $X_i$, $Y_i$, and $V_i$.
Each island has distinct coordinates. It is guaranteed that there are islands at coordinates $(1,1)$ and $(M,M)$.

Output Format

Output a single integer on the first line, representing the maximum net gain.

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

-4

Hint

Sample Explanation: $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$

Constraints:

• For $20\%$ of the testdata, $M\le 200$, and $N\le 2\times 10^3$.
• For $50\%$ of the testdata, $M\le 200$, and $N\le 2\times 10^4$.
• For $100\%$ of the testdata, $M\le 1000$, and $N\le 2\times 10^5$.

Translated by ChatGPT 5