Intervals from Triplets

Limits: 3 sec., 512 MiB

You are given \(n\) 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 \(n\) 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 \(n\) – the number of triplets.

The next \(n\) lines contain three integers \(a_i\), \(b_i\), and \(c_i\) – the \(i\)-th triplet.

Output

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

Constraints

\(1 \le n \le 10^6\),

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

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 3 2 3 5 7 8 9 4 7 8	7

Input (stdin) сopy	Output (stdout) сopy
3 1 2 4 1 2 4 1 2 4	-1

Notes

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: \((1, 2)\), \((2, 3)\), \((7, 9)\), \((4, 7)\). 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.