Study Schedule

Version: Phuoc Hung OJ Extended

Problem Statement

During one day, the team computer room has $N$ usage proposals. Proposal $i$ occupies the room continuously from time $S_i$ to time $T_i$ and gives value $V_i$ if selected.

Only one proposal can use the room at a time, so selected proposals must not overlap. If one proposal ends exactly when another begins, both may be selected.

Choose a set of proposals with maximum total value.

Input

• The first line contains the positive integer $N$.
• The next $N$ lines contain three integers $S_i,T_i,V_i$.

For every $i$: $0 \le S_i < T_i \le 10^9$ and $1 \le V_i \le 10^9$.

Output

Print one integer: the maximum total value obtainable.

Subtasks

• Subtask 1 (30%): $1 \le N \le 20$.
• Subtask 2 (30%): $1 \le N \le 2000$.
• Subtask 3 (40%): $1 \le N \le 2\cdot 10^5$.

Examples

Example 1

Input

5
1 3 5
2 5 6
4 6 5
6 7 4
5 8 11

Output

17

Explanation

Choose $[2,5]$ with value $6$ and $[5,8]$ with value $11$. They only touch at time $5$, so they are compatible, giving total $17$.

Example 2

Input

4
1 2 4
2 4 5
1 4 10
4 6 3

Output

13

Explanation

Choose $[1,4]$ with value $10$ and $[4,6]$ with value $3$, for a total of $13$.

Example 3

Input

3
1 10 7
2 3 4
3 4 4

Output

8

Explanation

Intervals $[2,3]$ and $[3,4]$ are compatible and give total $8$, which is better than taking only $[1,10]$ with value $7$.