Thợ mỏ kim cương

Có $n$ người thợ mỏ và $n$ mỏ kim cương nằm trên một mặt phẳng toạ độ.

• Mỗi người thợ mỏ là một điểm nằm trên trục $Oy$ (tức có hoành độ bằng $0$).
• Mỗi mỏ kim cương là một điểm nằm trên trục $Ox$ (tức có tung độ bằng $0$).

Không có điểm nào trùng với gốc toạ độ $(0,0)$.

Mỗi người thợ mỏ phải khai thác đúng một mỏ kim cương, và mỗi mỏ được khai thác bởi đúng một người thợ (một phép ghép cặp một-một giữa thợ và mỏ). Nếu một người thợ ở vị trí $(a,b)$ khai thác mỏ ở vị trí $(c,d)$ thì chi phí năng lượng bỏ ra bằng khoảng cách Euclid giữa hai điểm:

$$\sqrt{(a-c{)}^2+(b-d{)}^2}.$$

Hãy tìm cách ghép cặp sao cho tổng chi phí năng lượng của tất cả người thợ là nhỏ nhất, và in ra giá trị nhỏ nhất đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$.
  • $2n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ mô tả một điểm $(x,y)$. Nếu $x=0$ thì đây là một người thợ mỏ ở $(0,y)$; nếu $y=0$ thì đây là một mỏ kim cương ở $(x,0)$. Có thể có nhiều thợ hoặc nhiều mỏ nằm cùng một vị trí.

Đảm bảo số điểm nằm trên trục $Ox$ bằng $n$ và số điểm nằm trên trục $Oy$ cũng bằng $n$, và không điểm nào ở gốc toạ độ.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số thực là tổng chi phí năng lượng nhỏ nhất.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá ${10}^{-9}$.

Ràng buộc

• $1\le t\le 10$
• $1\le n\le {10}^5$
• $-{10}^8\le x,y\le {10}^8$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ

(Trong ví dụ đầu $t=1$ để minh hoạ một bộ dữ liệu; định dạng thực tế cho phép nhiều bộ.)