กำหนดสิ่งอันดับสามของจำนวนเต็ม $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$ ในตัวอย่างที่สอง เป็นไปไม่ได้ที่จะเลือกช่วงให้สอดคล้องกับเงื่อนไข