Description

JP does not train properly, and he has become addicted to another game—treasure hunting.

In the game, there are $n$ treasures buried in an infinite 2D grid. Each treasure has value $P_i$ and is located at $(x_i, y_i)$.

A grid cell $(x, y)$ is diggable if it satisfies one of the following conditions:

• $y = -1$.
• The three cells $(x-1, y+1)$, $(x, y+1)$, and $(x+1, y+1)$ have all been dug already.

The cost to dig one cell is $1$. When a treasure is dug out, you are considered to have obtained its value. Please help JP find the maximum profit, i.e., value minus cost. (It is also possible to dig no treasure, with profit $0$.)

Input Format

The first line contains $n$, the number of treasures.

The next $n$ lines each contain three integers $x_i, y_i, P_i$, representing the position and value of a treasure.

Output Format

Output one integer in a single line, representing the maximum profit.

5
1 -1 2
0 -1 2
4 -1 1
3 -1 2
2 -1 2

4

Hint

Sample Explanation 1

Dig treasures No. $1, 2, 4, 5$. The total value is $8$, the total cost is $4$, so the profit is $4$. It can be proven that there is no better plan.

Constraints

For $30\%$ of the testdata, $n \leq 15$.

For $50\%$ of the testdata, $-10^3 \leq y_i \leq 0$.

For $100\%$ of the testdata, $n \leq 10^3$, $-10^4 \leq x_i \leq 10^4$, $-10^4 \leq y_i < 0$, $1 \leq P_i \leq 10^6$.

Translated by ChatGPT 5