Xếp hàng

Để trình diễn một tiết mục trong màn khai mạc Đại hội thể thao quốc tế, đạo diễn X đã mời $n$ vận động viên tham gia. Theo kịch bản, $n$ vận động viên sẽ được xếp thành một hàng dọc hoặc một hàng ngang liên tiếp (song song với trục tọa độ). Hiện tại, vận động viên thứ $i$ đang ở vị trí $(x_i,y_i)$, nếu vận động viên này di chuyển đến vị trí $(u_i,v_i)$ thì sẽ mất năng lượng là $|x_i-u_i|+|y_i-v_i|$.

Hàng ngang liên tiếp là $n$ điểm nguyên $(a,c),(a+1,c),\dots ,(a+n-1,c)$; hàng dọc liên tiếp là $n$ điểm nguyên $(c,a),(c,a+1),\dots ,(c,a+n-1)$, với $a,c$ là các số nguyên tùy chọn. Mỗi điểm của hàng có đúng một vận động viên đứng, và ai đứng ở vị trí nào trong hàng cũng được. Ban đầu nhiều vận động viên có thể đứng cùng một vị trí.

Yêu cầu: Hãy giúp đạo diễn xác định cách xếp hàng để tổng năng lượng di chuyển của cả $n$ vận động viên là nhỏ nhất.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương $n$.
• Tiếp theo là $n$ dòng, dòng thứ $i$ chứa hai số nguyên $x_i,y_i$, các số có giá trị tuyệt đối không vượt quá ${10}^9$.

Dữ liệu ra

Gồm một dòng chứa một số nguyên là tổng năng lượng di chuyển nhỏ nhất của cả $n$ vận động viên.

Ràng buộc

• $1\le n\le {10}^5$.
• $|x_i|,|y_i|\le {10}^9$.

Subtasks

• $30\%$ số test: $0\le x_i,y_i\le {10}^2$, $n\le {10}^2$.
• $30\%$ số test: $0\le x_i,y_i\le {10}^4$, $n\le {10}^4$.
• $40\%$ số test: $n\le {10}^5$.

Ví dụ