Intervals from Triplets#13014

Intervals from Triplets

3 seconds
512 megabytes
Hard

You are given triplets of integers (a_i, b_i, c_i), such that a_i < b_i < c_i.

You have to choose a pair of values from each triplet and therefore form intervals. You need to choose pairs such that every two distinct intervals have zero intersection length.

Find the maximum possible sum of lengths of intervals, or tell that it is impossible to choose intervals satisfying the condition.

Input

The first line contains one integer – the number of triplets.

The next lines contain three integers a_i, b_i, and c_i – the -th triplet.

1 \le n \le 10^6,

1 \le a_i < b_i < c_i \le 10^9.

Output

If it is impossible to form intervals that satisfy the condition, print -1. Otherwise, print the maximum possible sum of lengths of intervals.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

In the first sample, there are n=4 triplets: (1, 2, 3), (2, 3, 5), (7, 8, 9), and (4, 7, 8).

One optimal solution is: , , , . These intervals satisfy the condition that every two distinct intervals have zero intersection length. The sum of their lengths is (2-1)+(3-2)+(9-7)+(7-4)=1+1+2+3=7.

In the second sample, it is impossible to choose the intervals satisfying the condition.