Вам задано $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$.
Приклади
Вхідні дані 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Вихідні дані 1
7
Вхідні дані 2
3 1 2 4 1 2 4 1 2 4
Вихідні дані 2
-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$. У другому прикладі вибрати відрізки, що задовольняють умову, неможливо.