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