개미

어린 자연주의자 Bill은 학교에서 개미를 연구한다. Bill의 개미들은 사과나무에 사는 진딧물을 먹고 살며, 각 개미 군집은 먹이를 얻기 위해 자기만의 사과나무 한 그루가 필요하다.

Bill은 $n$개의 개미 군집과 $n$그루의 사과나무의 좌표가 표시된 지도를 가지고 있다. 그는 각 개미 군집을 서로 다른 사과나무 한 그루와 정확히 하나씩 연결하려고 한다.

좌표 $(x_c, y_c)$에 있는 군집을 좌표 $(x_t, y_t)$에 있는 사과나무와 연결하는 비용은 두 점 사이의 유클리드 거리의 제곱으로 정의한다:

$(x_c - x_t)^2 + (y_c - y_t)^2.$

$n$개의 군집과 $n$그루의 나무를 일대일로 짝지을 수 있는 모든 방법 중에서, 전체 비용의 합이 최소가 되도록 할 때 그 최솟값을 구하라.

그림에서 개미 군집은 빈 원으로, 사과나무는 채워진 원으로 나타내며, 선은 하나의 가능한 짝짓기를 보여준다.

첫째 줄에 개미 군집과 사과나무의 개수 $n$ ($1 \le n \le 100$)이 주어진다.

이어지는 $n$개의 줄에는 개미 군집이, 그다음 $n$개의 줄에는 사과나무가 주어진다. 각 군집과 나무는 데카르트 평면 위의 정수 좌표 $x$, $y$ ($-10\,000 \le x, y \le 10\,000$)로 표현된다. $2n$개의 점은 모두 서로 다르다.

각 개미 군집을 서로 다른 사과나무 한 그루와 짝지을 때, 전체 연결 비용의 합의 최솟값을 정수 하나로 출력한다. 하나의 연결 비용은 군집과 나무 사이의 유클리드 거리의 제곱이다.