A hungry frog is going to hunt flies. It has stationed itself on one side of a pond that has $n$ rocks in it numbered $1,2,\dots,n$. On the $i$-th rock there are $a_i$ flies flying around it. From the $i$-th rock the frog can jump forward to any of the rocks between $b_i$ and $c_i$ inclusive. Find the maximum number of flies the frog can catch. Initially, the frog can jump on to any of the rocks.

Input

The first line contains a single integer $n$. The $i$-th of next $n$ following lines contains three integers $a_i$, $b_i$, and $c_i$.

Output

Print the maximum number of flies the frog can catch.

Constraints

• $1 \leq n \leq 10^5$
• $i \leq b_i \leq c_i \leq n$
• $1 \leq a_i \leq 10^9$

Example 1

Input:

4
9 1 1
11 2 4
13 3 3
19 4 4

Output:

30

Example 2

Input:

10
19 8 10
7 2 3
5 4 10
4 4 6
14 7 7
11 7 10
7 8 10
5 9 10
5 9 10
14 10 10

Output:

61