$a_i < b_i < c_i$를 만족하는 정수의 삼중쌍 $(a_i, b_i, c_i)$가 $n$개 주어집니다. 각 삼중쌍에서 두 개의 값을 선택하여 총 $n$개의 구간을 만들어야 합니다. 이때 서로 다른 임의의 두 구간의 교집합의 길이가 0이 되도록 쌍을 선택해야 합니다. 구간들의 길이의 합의 최댓값을 구하거나, 조건을 만족하도록 구간을 선택하는 것이 불가능함을 판별하시오.
입력
첫 번째 줄에 삼중쌍의 개수를 나타내는 정수 $n$이 주어집니다. 다음 $n$개의 줄에는 $i$번째 삼중쌍을 나타내는 세 정수 $a_i$, $b_i$, $c_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)$입니다. 이 구간들은 서로 다른 임의의 두 구간의 교집합의 길이가 0이라는 조건을 만족합니다. 구간 길이의 합은 $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$입니다. 두 번째 예제에서는 조건을 만족하도록 구간을 선택하는 것이 불가능합니다.