Treasure Map Journey

jyy has discovered a treasure map on Mars, which hints that the treasure is hidden on N islands located in a huge lake. The lake is divided into M rows and M columns of square cells. Each island is given a unique number from 1 to N. The i-th island is located at cell \( (X_i, Y_i) \) (with \(1 \le X_i, Y_i \le M\)) and contains fruits with a value of \(V_i\) (\(1 \le V_i \le 10{,}000\)). It is guaranteed that there is an island at the top-left cell \((1,1)\) and at the bottom-right cell \((M,M)\). A bridge connects these two islands with the mainland.

jyy starts his journey at the island located at \((1,1)\) where he finds a small boat. He can travel between islands by boat and collect the fruits. However, moving from one island to another consumes energy. In particular, if jyy goes from island \((X_1, Y_1)\) to island \((X_2, Y_2)\), the energy consumed is equal to the square of the Euclidean distance:

[ \text{Energy cost} = (X_1 - X_2)^2 + (Y_1 - Y_2)^2. ]

At any point during his journey, jyy may accumulate negative energy (i.e. he may get 'hungry'), but he can always eat fruits to restore his energy at the end. Specifically, after reaching the destination at \((M, M)\), he will consume some of the fruits he collected (each unit value of fruit restores 1 unit of energy) to make up for the energy deficit accumulated during the journey.

Following the treasure map’s hint, once jyy leaves an island, he can only travel to islands that are in the bottom-right region (i.e. the next island's coordinates must satisfy \(X_2 \ge X_1\) and \(Y_2 \ge Y_1\); note that moving strictly right or strictly down is allowed).

The net gain of a journey is defined as the total value of fruits collected minus the total energy spent traveling between islands. jyy wants to know what is the maximum net gain he can achieve on a journey from \((1,1)\) to \((M,M)\).

inputFormat

The first line contains two integers N and M, where \(2 \le N \le 2 \times 10^5\) and \(1 \le M \le 1000\). Each of the following N lines contains three integers \(X_i\), \(Y_i\) and \(V_i\), indicating that the i-th island is located at \((X_i, Y_i)\) and contains fruits of value \(V_i\). It is guaranteed that there is an island at \((1, 1)\) and at \((M, M)\).

outputFormat

Print a single integer representing the maximum net gain jyy can achieve. The net gain is defined as the total fruits collected minus the total energy cost during the journey. Note that the net gain may be negative if the energy cost exceeds the total fruits collected.

sample

2 3
1 1 5
3 3 10

7