Uolevi is working at a giant megacorporation's warehouse. Now that he has stacked all the boxes that contain items, 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 holds for 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 i-th of the next n lines contains three integers x_i, y_i, 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