THỰC HÀNH

Trong nhà hàng “Siêu nhân” có hai chú robots hầu bàn rất đắc lực có tên là Cuội và Bờm. Đây là các sản phẩm mới nhất của hãng Cybernetic. Nhiệm vụ của robot là đến bàn có khách hàng và hỏi các thực khách xem họ cần dùng đồ ăn uống gì. Sau khi nhận được đơn đặt hàng của thực khách, robot sẽ gửi thông điệp vào bộ phận nhà bếp để các đầu bếp chuẩn bị các món theo đơn đặt hàng của thực khách, rồi di chuyển đến bàn tiếp theo. Khi đồ ăn uống đã sẵn sàng, chúng sẽ được chuyển theo đường dẫn đặc biệt đến bàn của thực khách.

Cuội và Bờm sẽ chia nhau làm việc, mỗi thực khách sẽ được phục vụ bởi một trong hai robot. Vì hai robot này cũng rất lười di chuyển, nên chúng lên kế hoạch phục vụ rất cẩn thận. Một số thực khách sẽ được phục vụ bởi Bờm, số còn lại được phục vụ bởi Cuội và mục tiêu là tìm cách phân công sao cho tổng độ dài quãng đường phải di chuyển bởi hai robot là nhỏ nhất. Hai robot phải tỏ thái độ lịch sự đối với thực khách, vì thế chúng phục vụ thực khách theo nguyên tắc: Ai đến trước được phục vụ trước. Nghĩa là: nếu thực khách A đến lúc 8:00 còn thực khách B đến lúc 9:00 thì Bờm không được phục vụ thực khách B trước thực khách A. Tuy nhiên, cho phép Cuội phục vụ thực khách B trước, còn Bờm phục vụ thực khách A ở thời điểm muộn hơn: nghĩa là trình tự trên chỉ cần tuân thủ đối với những thực khách được phục vụ bởi cùng một robot.

Yêu cầu: Cho biết vị trí của các thực khách, hãy tìm cách phân công hai robot phục vụ sao cho tổng khoảng cách mà hai robot phải di chuyển là nhỏ nhất.

Input:

• Dòng đầu tiên ghi số nguyên n (1 ≤ n ≤ 500) là số lượng thực khách trong nhà hàng.
• Dòng thứ hai ghi hai số nguyên x₁, y₁ (cách nhau bởi dấu cách) là vị trí ban đầu của Cuội.
• Dòng thứ ba ghi hai số nguyên x₂, y₂ (cách nhau bởi dấu cách) là vị trí ban đầu của Bờm.
• Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên x, y là toạ độ của khách hàng thứ i (các khách hàng được liệt kê theo thứ tự mà họ đến nhà hàng).

Các toạ độ là các số nguyên không âm không vượt quá 2000.

Output:

Ghi trên một dòng một số nguyên là tổng khoảng cách mà hai robot phải di chuyển theo cách phân công tìm được được làm tròn xuống đến số nguyên gần nhất.

Ví dụ:

Input:
2
100 200
200 200
0 200
100 300
Output:
241

Giải thích: Có thể phân công như sau: Bờm đến phục vụ thực khách 1, Cuội đến phục vụ thực khách 2 (Hoặc Bờm đến phục vụ thực khách 1 sau đó đến phục vụ thực khách 2, Cuội không phải phục vụ thực khách nào).

Ghi chú: Khoảng cách giữa hai điểm A(x_A, y_A) và B(x_B, y_B) được tính bởi: