P6249 Legendary Post

zrl's birthday is on 3.14. Born on a day full of legendary posts, he naturally has a lot of happiness. Now, he is going to receive gifts from those legendary posts again.

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.**

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.

One integer, the maximum happiness value zrl can obtain.

#### 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 | Test Point | Special Property | | :-----------: | :-----------: | | $1-2$ | $x_i \ge 0$ | | $3-4$ | $0 \le t_i \le 20$ | | $5-6$ | $n \le 20$ | | $7$ | $-10 \le x_i \le 10$ | | $8-9$ | $t_i =$\|$x_i$\| | | $10-13$ | all $t_i$ are equal | | $14-17$ | $n \le 60$ | | $17-22$ | none | 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