Відрізки з трійок

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

Вам задано \(n\) трійок цілих чисел \((a_i, b_i, c_i)\), де \(a_i < b_i < c_i\).

З кожної трійки потрібно вибрати пару чисел і таким чином утворити \(n\) відрізків.

Необхідно вибрати пари так, щоб будь-які два різні відрізки мали нульову довжину перетину.

Знайдіть максимально можливу суму довжин відрізків або повідомте, що вибрати відрізки, які задовольняють цю умову, неможливо.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість трійок.

У наступних \(n\) рядках задано по три цілі числа \(a_i\), \(b_i\) та \(c_i\) — \(i\)-ту трійку.

Вихідні дані

Якщо неможливо утворити відрізки, що задовольняють умову, виведіть -1. Інакше виведіть максимальну можливу суму довжин відрізків.

Обмеження

\(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

Примітки

У першому прикладі задано \(n=4\) трійки: \((1, 2, 3)\), \((2, 3, 5)\), \((7, 8, 9)\) та \((4, 7, 8)\).

Одним з оптимальних варіантів є відрізки \((1, 2)\), \((2, 3)\), \((7, 9)\) та \((4, 7)\). Ці відрізки задовольняють умову, що будь-які два різні відрізки мають нульову довжину перетину. Сума їхніх довжин дорівнює \((2-1)+(3-2)+(9-7)+(7-4)=1+1+2+3=7\).

У другому прикладі неможливо вибрати відрізки, що задовольняють умову.