Bạn được cho $n$ bộ ba số nguyên $(a_i, b_i, c_i)$, sao cho $a_i < b_i < c_i$. Bạn phải chọn một cặp giá trị từ mỗi bộ ba và từ đó tạo thành $n$ đoạn thẳng. Bạn cần chọn các cặp sao cho mỗi hai đoạn thẳng phân biệt có độ dài phần giao bằng không. Hãy tìm tổng độ dài lớn nhất có thể của các đoạn thẳng, hoặc cho biết không thể chọn được các đoạn thẳng thỏa mãn điều kiện.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ — số lượng bộ ba. $n$ dòng tiếp theo chứa ba số nguyên $a_i$, $b_i$ và $c_i$ — bộ ba thứ $i$.
Kết quả
Nếu không thể tạo thành các đoạn thẳng thỏa mãn điều kiện, hãy in ra -1. Ngược lại, in ra tổng độ dài lớn nhất có thể của các đoạn thẳng.
Giới hạn
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Ví dụ
Dữ liệu vào 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Kết quả 1
7
Dữ liệu vào 2
3 1 2 4 1 2 4 1 2 4
Kết quả 2
-1
Ghi chú
Trong ví dụ đầu tiên, có $n = 4$ bộ ba: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$, và $(4, 7, 8)$. Một phương án tối ưu là: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Các đoạn thẳng này thỏa mãn điều kiện mỗi hai đoạn thẳng phân biệt có độ dài phần giao bằng không. Tổng độ dài của chúng là $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. Trong ví dụ thứ hai, không thể chọn được các đoạn thẳng thỏa mãn điều kiện.