Description

Legendary posts are distributed on some pages in the forum, and each page has at most one legendary post. Suppose the page he is currently browsing is page $0$. One page to the left is page $-1$, and one page to the right is page $1$, and so on. The $i$-th legendary post is on page $x_i$, and it has a specific ban time $t_i$ and happiness value $v_i$. If he browses it after time $t_i$, he cannot get its happiness value. It takes $1$ unit of time for zrl to flip one page left or right, and browsing a legendary post takes no time. Ask: what is the maximum total happiness value zrl can obtain.

Note: If he browses the $i$-th legendary post at exactly $t_i$ units of time, he can still get $v_i$ happiness value.

Additional note: the happiness value of each legendary post can be obtained at most once.

Input Format

The first line contains an integer $n$, indicating the number of legendary posts.

The next $n$ lines each contain three integers, representing $x_i$, $v_i$, and $t_i$ of the $i$-th legendary post.

Output Format

One integer, the maximum happiness value zrl can obtain.

5
-5 1 5
-3 1 5
-1 1 5
1 1 5
3 2 5

4

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

5

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

5

Hint

Sample Explanation

Sample 1: $0 \rightarrow -1 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 3$
Sample 2: $0 \rightarrow -1 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 3$
Sample 3: $0 \rightarrow -1 \rightarrow -2 \rightarrow -3 \rightarrow -4 \rightarrow -5$

Constraints

For $100\%$ of the testdata: $n \le 200$, $-500 \le x_i \le 500$, $0 \le v_i \le 10^9$, $0 \le t_i \le 500$.

Hint: Two new groups of hack testdata have been added, so greedy/simulation can no longer pass.

Translated by ChatGPT 5