Uolevi works at a giant megacorporation warehouse. Now that he has stacked all the boxes that have stuff in them, he is going to build the tallest possible pyramid from the empty boxes. There are $n$ boxes numbered $1,2,\dots,n$, the $i$-th of which has width $x_i$, depth $y_i$ and height $z_i$. A tower of boxes is called a pyramid if $x_i \leq x_j$ and $y_i \leq y_j$ applies to all pairs of boxes $(i, j)$ where box $i$ is on top of box $j$. Find the height of the tallest possible pyramid Uolevi can construct.

Input

The first line contains a single integer $n$. The $𝑖$-th of the next $n$ lines contains three integers $x_i$, $y_𝑖$, and $z_i$.

Output

Print the height of the tallest possible pyramid.

Constraints

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq x_i, y_i, z_i \leq 10^9$

Example 1

Input:

5
5 10 8
10 1 2
4 10 2
3 1 4
2 4 4

Output:

14

Example 2

Input:

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

Output:

33

Example 3

Input:

1
1000000000 1000000000 1000000000

Output:

1000000000