Maximum Happiness Collection

You are given several special posts distributed on different pages of an online forum. Each page contains at most one special post. The pages are numbered by integers: page 0 is the initially viewed page, page -1 is immediately to the left of page 0, page 1 is immediately to the right, and so on. The i-th special post is located on page (x_i) and comes with two numbers: a deadline (t_i) and a happiness value (v_i). If you visit the page containing the post no later than time (t_i) (that is, if your current time (\tau) satisfies (\tau \le t_i)), you obtain its happiness value (v_i). Otherwise, you gain nothing from that post. Note that if you visit exactly at time (t_i), you still gain the happiness value. Also, each post’s happiness value can be collected at most once.

At the beginning, you are at page 0 and time 0. Flipping one page to the left or right takes exactly 1 unit of time. Browsing (i.e. collecting a post on that page) takes no extra time. There may be a post on page 0; if so, you collect its happiness value immediately (provided (0 \le t_i), which is always true under the constraints).

Determine the maximum total happiness you can collect by planning an optimal route.

Input constraints:

• The first line contains an integer \(n\) \( (1 \le n)\), the number of posts.
• Each of the following \(n\) lines contains three integers: \(x\), \(t\), and \(v\), representing respectively the page number, the deadline, and the happiness value of a post.

Note: The deadlines and positions are such that an optimal solution can be found using dynamic programming on the line. Any formula should be written in (\LaTeX) format, for example: reaching a post at page (p) at time (\tau) is subject to the condition (\tau \le t).

Example: If the input is:

3
0 0 10
1 5 5
-1 3 7

Then one optimal route is:

1. Start at page 0: collect 10 happiness (post on page 0).
2. Move left to page -1 (time = 1), collect 7 happiness because \(1 \le 3\).
3. Then move from page -1 to page 1 (distance = 2, time becomes 3), collect 5 happiness because \(3 \le 5\).

The total happiness is \(10+7+5=22\).

Your task is to output the maximum total happiness that can be obtained.

inputFormat

The first line contains an integer (n), the number of posts. Each of the next (n) lines contains three integers (x), (t), and (v), where (x) is the page number, (t) is the deadline for collecting the happiness value, and (v) is the happiness value of the post. Note that if (x = 0), the post is on the starting page and is collected immediately at time 0.

outputFormat

Output a single integer — the maximum total happiness that can be collected.

sample

3
0 0 10
1 5 5
-1 3 7

22