Marathon

Một cuộc chạy marathon gồm $N$ trạm kiểm soát phải đi qua theo thứ tự. Khoảng cách giữa hai điểm $(x_1,y_1)$ và $(x_2,y_2)$ là khoảng cách Manhattan: $|x_1-x_2|+|y_1-y_2|$.

Bạn được phép bỏ qua tối đa một trạm kiểm soát (trừ trạm đầu và trạm cuối) để giảm thiểu tổng quãng đường chạy.

Hãy tính tổng quãng đường ngắn nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$.

• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$ — tọa độ trạm thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất — tổng quãng đường ngắn nhất.

Ràng buộc

• $3\le N\le 100000$
• $-1000\le x_i,y_i\le 1000$

Ví dụ