กำหนดคู่จำนวนเต็ม $(a_i,b_i)$ จำนวน $2n$ คู่ พิจารณากราฟบริบูรณ์ที่มีจุดยอด $2n$ จุด และนิยามน้ำหนักของเส้นเชื่อม $(ij)$ เป็น $w_{ij}=\max(|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|)$

จงหาน้ำหนักสูงสุดของการจับคู่ในกราฟนี้

กล่าวอีกนัยหนึ่ง ให้พิจารณาทุกวิธีในการเลือกเส้นเชื่อม $n$ เส้นจากกราฟนี้ โดยไม่มีเส้นเชื่อมที่เลือกสองเส้นใดมีจุดปลายร่วมกัน น้ำหนักรวมสูงสุดที่เป็นไปได้ของเส้นเชื่อมเหล่านี้เป็นเท่าใด?

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวน $n$ ($1\le n\le 10^5$)

บรรทัดที่ $i$ ใน $2n$ บรรทัดถัดมาประกอบด้วยจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ ($0\le a_i,b_i\le 10^9$)

ข้อมูลส่งออก

พิมพ์จำนวนเต็มหนึ่งจำนวน ซึ่งเป็นน้ำหนักสูงสุดของการจับคู่ในกราฟนี้

ตัวอย่าง

ข้อมูลนำเข้า 1

2
0 10
7 7
9 4
2 15

ข้อมูลส่งออก 1

18

หมายเหตุ

เมทริกซ์ประชิด: $$\begin{matrix}0&7&9&15\\7&0&3&8\\9&3&0&11\\15&8&11&0\end{matrix}$$