Problem Description

There are $n$ robbers. The $i$-th robber will choose one time slot of length $1$ to rob from the following intervals: $[a_i, a_i + 1], [a_i + 1, a_i + 2], \cdots, [b_i - 1, b_i]$, and plans to steal $c_i$ dollars. As a security guard, in each time slot of length $1$ you can stop at most one robber. What is the maximum loss you can recover?

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three integers $a_i, b_i, c_i$.

Output Format

One line containing an integer, representing the required value.

4
1 4 40
2 4 10
2 3 30
1 3 20

90

Hint

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^3$, $1 \leq a_i < b_i \leq 5 \times 10^3$, $1 \leq c_i \leq 10^4$.

Translated by ChatGPT 5