Intervals from Triplets

Обмеження: 3 сек., 512 МіБ

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.

Вхідні дані

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.

Вихідні дані

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

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 3 2 3 5 7 8 9 4 7 8	7

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 1 2 4 1 2 4 1 2 4	-1

Примітки

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.