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

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

3 секунди
512 мегабайтів
Складна

Вам задано трійок цілих чисел (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. Інакше виведіть максимальну можливу суму довжин відрізків.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі задано 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.

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