Không hài lòng với tình trạng sức khỏe kém của đàn bò, Farmer John đăng ký cho chúng tham gia nhiều hoạt động rèn luyện thể chất khác nhau. Cô bò quý Bessie của ông tham gia một lớp chạy bộ, nơi cô được kỳ vọng cuối cùng sẽ chạy một cuộc marathon qua khu trung tâm của thành phố gần trang trại của Farmer John!

Đường chạy marathon gồm \(N\) checkpoint (\(3 \le N \le 100\,000\)) phải được ghé thăm theo thứ tự, trong đó checkpoint 1 là điểm xuất phát và checkpoint \(N\) là đích đến. Bessie lẽ ra phải lần lượt đi qua tất cả các checkpoint này, nhưng vì là một cô bò lười biếng, cô quyết định sẽ bỏ qua nhiều nhất một checkpoint để rút ngắn tổng quãng đường. Tuy nhiên, cô không thể bỏ qua checkpoint 1 hoặc checkpoint \(N\), vì làm vậy sẽ quá dễ bị phát hiện.

Hãy giúp Bessie tìm quãng đường ngắn nhất mà cô phải chạy nếu được bỏ qua nhiều nhất một checkpoint.

Lưu ý rằng vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\). Cách đo khoảng cách này — lấy độ chênh lệch theo \(x\) cộng với độ chênh lệch theo \(y\) — đôi khi được gọi là khoảng cách “Manhattan”, vì trong một mạng lưới đường phố ở trung tâm thành phố, ta có thể di chuyển song song với trục \(x\) hoặc trục \(y\), nhưng không thể đi theo đường thẳng trực tiếp “như chim bay”.

Dữ liệu vào

Dòng đầu tiên chứa giá trị \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) cách nhau bởi dấu cách, biểu diễn một checkpoint (\(-1000 \le x \le 1000\), \(-1000 \le y \le 1000\)). Các checkpoint được cho theo đúng thứ tự phải ghé thăm. Lưu ý rằng đường chạy có thể tự cắt nhau nhiều lần, và nhiều checkpoint có thể nằm tại cùng một vị trí thực tế. Khi Bessie bỏ qua một checkpoint như vậy, cô chỉ bỏ qua một lần xuất hiện của checkpoint đó, chứ không bỏ qua mọi checkpoint nằm tại cùng vị trí.

Dữ liệu ra

In ra quãng đường ngắn nhất Bessie có thể chạy khi được bỏ qua nhiều nhất một checkpoint. Đừng quên kết thúc dữ liệu ra bằng một ký tự xuống dòng.

Ví dụ

4
0 0
8 3
11 -1
10 0

14

Nguồn

USACO 2014 December Contest, Bronze — Marathon. Tác giả đề: Nick Wu, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=487