Вам задано трійок цілих чисел (a_i, b_i, c_i), де a_i < b_i < c_i.
З кожної трійки потрібно вибрати пару чисел і таким чином утворити відрізків.
Необхідно вибрати пари так, щоб будь-які два різні відрізки мали нульову довжину перетину.
Знайдіть максимально можливу суму довжин відрізків або повідомте, що вибрати відрізки, які задовольняють цю умову, неможливо.
У першому рядку задано ціле число — кількість трійок.
У наступних рядках задано по три цілі числа a_i, b_i та c_i — -ту трійку.
1 \le n \le 10^6,
1 \le a_i < b_i < c_i \le 10^9.
Якщо неможливо утворити відрізки, що задовольняють умову, виведіть -1. Інакше виведіть максимальну можливу суму довжин відрізків.
Приклад
Приклад 1
У першому прикладі задано n=4 трійки: (1, 2, 3), (2, 3, 5), (7, 8, 9) та (4, 7, 8).
Одним з оптимальних варіантів є відрізки , , та . Ці відрізки задовольняють умову, що будь-які два різні відрізки мають нульову довжину перетину. Сума їхніх довжин дорівнює (2-1)+(3-2)+(9-7)+(7-4)=1+1+2+3=7.
У другому прикладі неможливо вибрати відрізки, що задовольняють умову.