Problem C
Weighted Interval Scheduling

A set of $8$ weighted intervals corresponding to sample input 2. The maximum total weight of nonoverlapping intervals is $12$, achieved by the highlighted intervals.

Consider a set of $n$ weighted intervals $I_1,\ldots , I_ n$, each given as an integer tuple $(s_ i, f_ i, w_ i)$ with $s_ i<f_ i$, such that the $i$th interval starts at $s_ i$, ends at $f_ i$, and has weight $w_ i$. We want to determine the maximum total weight of nonoverlapping intervals. More formally, we want to maximise $\sum _{i\in S} w_ i$ over the subsets $S\subseteq \{ 1,\ldots ,n\} $ such that for $i, j\in S$ with $i\neq j$ we have $f_ j \leq s_ i$ or $f_ i\leq s_ j$. Note that the intervals $[1,2]$ and $[2,3]$ are not considered to be overlapping.

Input

The first line of input consists of an integer $n\in \{ 1,\ldots , 10^5\} $, the number of intervals. Each of the following $n$ lines consists of three space-separated integers $s$, $f$, and $w$, indicating an interval starting at $s$, ending at $f$, and of weight $w$, with $0\leq s<f\leq 10^9$ and $1\leq w\leq 10^9$.

Output

Output a single integer $t$, the maximum total weight of a subset of the nonoverlapping intervals. You can assume $1\leq t\leq 10^9$.

3
1 4 1
2 8 3
5 9 1

3

8
0 6 3
1 4 2
3 5 1
3 8 6
4 7 7
5 9 1
6 10 4
8 11 3

12