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