Sau nhiều năm đạt sản lượng sữa kỷ lục, Nông dân John hiện điều hành cả một mạng lưới gồm \(N\) trang trại (\(1 \le N \le 100\)). Trang trại \(i\) nằm tại vị trí \((x_i,y_i)\) trên mặt phẳng hai chiều, khác với vị trí của mọi trang trại khác; cả \(x_i\) và \(y_i\) đều là số nguyên.

FJ cần bạn giúp lập kế hoạch cho lộ trình giao hàng hằng ngày để mang vật tư đến \(N\) trang trại. Bắt đầu từ trang trại \(1\), ông dự định lần lượt ghé thăm các trang trại (trang trại \(1\), rồi trang trại \(2\), sau đó trang trại \(3\), v.v.), cuối cùng quay lại trang trại \(1\) sau khi ghé trang trại \(N\). FJ mất một phút để đi một bước theo hướng bắc, nam, đông hoặc tây. Hơn nữa, FJ muốn ghé mỗi trang trại đúng một lần trong toàn bộ hành trình (tất nhiên ngoại trừ trang trại \(1\), nơi ông ghé hai lần).

Hãy giúp FJ xác định thời gian nhỏ nhất để hoàn thành toàn bộ lộ trình giao hàng.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng trang trại \(N\).
• \(N\) dòng tiếp theo; dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) cách nhau bởi dấu cách (\(1 \le x_i,y_i \le 1\,000\,000\)).

Dữ liệu ra

• Dòng đầu tiên chứa số phút nhỏ nhất FJ cần để hoàn thành lộ trình giao hàng, hoặc -1 nếu không thể tìm được một lộ trình hợp lệ ghé mỗi trang trại đúng một lần (ngoại trừ trang trại \(1\)).

Ví dụ

4
2 2
2 4
2 1
1 3

12

Nguồn

USACO 2012 January Contest, Silver Division — Delivery Route

Tác giả đề: Brian Dean, 2012.