Thu gom vỏ chai

Adil và Bera đi thu gom vỏ chai ở công viên trong ngày hội tái chế. Công viên được mô tả như mặt phẳng tọa độ: Adil đứng ở vị trí $(a_x,a_y)$, Bera đứng ở vị trí $(b_x,b_y)$, thùng rác tái chế đặt tại $(t_x,t_y)$. Trên mặt đất có $n$ vỏ chai, vỏ chai thứ $i$ nằm ở vị trí $(x_i,y_i)$.

Mỗi người chỉ mang được một vỏ chai mỗi lượt. Quá trình của mỗi người diễn ra như sau:

1. Chọn dừng lại hoặc tiếp tục nhặt vỏ chai.
2. Nếu tiếp tục, chọn một vỏ chai còn trên mặt đất và đi thẳng tới đó.
3. Nhặt vỏ chai đó rồi đi thẳng tới thùng rác để bỏ vào.
4. Quay lại bước 1.

Hai người di chuyển độc lập, có thể nhặt đồng thời; mỗi vỏ chai có thể do bất kỳ ai nhặt, và một người có thể đứng yên hoàn toàn trong khi người kia làm việc.

Hãy tính tổng quãng đường nhỏ nhất mà hai người cần đi (tổng quãng đường của Adil cộng quãng đường của Bera) sao cho cuối cùng mọi vỏ chai đều nằm trong thùng rác.

Dữ liệu vào

• Dòng đầu chứa sáu số nguyên $a_x,a_y,b_x,b_y,t_x,t_y$: vị trí ban đầu của Adil, Bera và thùng rác.
• Dòng thứ hai chứa số nguyên $n$: số vỏ chai.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i,y_i$: vị trí vỏ chai thứ $i$.

Dữ liệu ra

In ra một số thực duy nhất: tổng quãng đường nhỏ nhất. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $0\le a_x,a_y,b_x,b_y,t_x,t_y\le {10}^9$
• $1\le n\le {10}^5$
• $0\le x_i,y_i\le {10}^9$
• Vị trí của Adil, Bera, thùng rác và tất cả vỏ chai đôi một phân biệt.

Ví dụ