Background

zrl's birthday is on March 14th. Born during a time of divine posts, he naturally enjoys a lot of happiness. And now, he is about to receive gifts from these divine posts.

Problem Description

Divine posts are distributed across some pages of the discussion forum, with at most one divine post per page. Suppose the page he is currently browsing is page $0$. Moving one page to the left is page $-1$, and moving one page to the right is page $1$, and so on. The $i$-th divine post is on page $x_i$, has a specific ban time $t_i$, and a happiness value $v_i$. If he browses it after time $t_i$, he cannot gain its happiness value. zrl takes 1 unit of time to move one page left or right, and browsing a divine post does not take any time. The question is: what is the maximum happiness value zrl can gain?

Note: Browsing the $i$-th divine post at $t_i$ units of time still allows him to gain the happiness value $v_i$.

Additional Note: Each divine post's happiness value can only be gained once.

Input Format

The first line contains an integer $n$, representing the number of divine posts.

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

Output Format

An integer representing the maximum happiness value zrl can gain.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

5

Sample Input #3

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

Sample Output #3

5

Notes

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$

Data Range:

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

Hint: Two additional Hack data sets have been added; greedy/simulation approaches are no longer feasible.

见题面 Input 部分

见题面 Output 部分