소 확인 목록

농부 존은 매일 목장을 돌며 소의 상태를 확인한다. 목장에는 홀스타인과 건지, 두 품종이 있다. 홀스타인 $H$마리에는 1부터 $H$까지, 건지 $G$마리에는 1부터 $G$까지 번호가 붙어 있다 ($1 \le H \le 1000$, $1 \le G \le 1000$). 각 소는 2차원 평면의 한 점에 있고, 서로 다른 소가 같은 점에 있어도 된다.

존은 홀스타인 1번에서 출발해 홀스타인 $H$번에서 순회를 마친다. 그 사이에 모든 소를 정확히 한 번씩 방문하고, 확인 목록을 채우기 쉽도록 같은 품종은 번호가 작은 순서대로 방문한다. 즉 존이 방문한 $H+G$마리의 나열에서 홀스타인 1번부터 $H$번이 연속하지 않아도 되는 부분 수열로 나타나고, 건지도 똑같이 나타난다. 다르게 말하면 전체 방문 순서는 홀스타인 목록과 건지 목록을 하나로 섞어 놓은 나열이다.

한 소에서 다른 소로 거리 $D$만큼 이동하면 에너지를 $D^2$만큼 쓴다. 위 조건을 지키는 순회 가운데 필요한 에너지가 가장 적은 값을 구하라.

첫 줄에 $H$와 $G$가 공백으로 구분되어 주어진다.

다음 $H$개 줄에는 홀스타인의 $x$ 좌표와 $y$ 좌표가 번호 순서대로 주어지고, 그 뒤 $G$개 줄에는 건지의 좌표가 번호 순서대로 주어진다. 모든 좌표는 0 이상 1000 이하의 정수다. 조건을 만족하는 순회가 적어도 하나 존재하는 입력만 주어진다.

모든 소를 방문하는 데 필요한 에너지의 최솟값을 한 줄에 출력한다. 에너지의 합은 항상 정수다.