9043번 - Delivery 채점 준비 중

우리네 농부들은 예로부터 콩을 수확하기 위해 땅을 파고 콩 세 알을 묻었다. 한 알은 땅에 사는 벌레가 먹고, 한 알은 하늘을 날아다니다 먹이를 찾아 들르는 새가 먹고, 나머지 남은 한 알이 자라면 인간이 거두어들여 먹었다.

ICPC(Impressive Crab Porridge Corporation)는 게살죽을 전문적으로 팔면서 동시에 이웃 사랑을 직접 실천하는 사회적 기업이다. 어운동에 위치한 ICPC 는 주변 정남대학교와 가기대학교 학생들이 자주 찾는데 게살죽의 인상적인 맛을 알고 나서 단골이 된 학생이 많다. 몸이 안 좋을 때에 특히 생각나는데, 배달도 가능하다. 특히 밤샘 연구로 건강을 챙기기 힘든 주변 학교의 독거 대학원생들이 식사를 거르지 않도록 죽을 배달하는 무상 급식 사업을 벌이고 있다. 이는 나라의 미래에 조금이라도 보탬이 되고자 하는 사장 조송범씨의 사회적 기업 정신이다.

학생들의 생활에 조금이라도 보탬이 되도록 배달 아르바이트는 학생만을 대상으로 고용을 하는데, 맛있는 죽을 한정된 수의 고객에게 제공하다 보니 수지타산을 맞추기 빠듯하여 한 명의 배달원 만을 고용하고 있다. 이 한 명의 배달원이 주문 배달도 하면서 무상 급식 사업까지 도와준다. 특히 배달에 있어서 사장 조성범씨의 깐깐함이 묻어 나오는 것은 배달 순서에 있어서 선착순 원칙이다. 주문 배달에 대해서 먼저 주문한 사람에게 먼저 배달되어야 하며, 무상 급식에 있어서도 먼저 신청한 사람에게 먼저 배달되어야 한다. 단, 돈을 지불하는 주문 배달한 사람과 무상 급식을 신청한 사람의 순서는 무관하다. 예를 들어서, A, B, C 의 순서로 배달 주문이 들어오고 X, Y, Z 의 순서로 무상 급식 신청이 들어오게 되면 B 는 반드시 A 에게 배달된 다음에 배달되어야 하며 C 보다 먼저 배달을 받아야 하지만 X, Y, Z 의 배달 순서와는 상관이 없다.

ICPC 의 사회 서비스를 도와주기 위해, 한 명의 배달원이 배달 주문, 무상 급식 신청 두 가지 모두를 최단 거리로 배달할 수 있는 프로그램을 작성하시오. ICPC 에서 출발하며 ICPC 의 위치는 (0, 0)으로 가정한다.

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트케이스의 첫 줄에는 배달 주문의 수와 무상 급식 신청의 수 N (1 ≤ N ≤ 20), M (1 ≤ M ≤ 20)이 공백 하나를 사이에 두고 주어진다. 그 다음 N 줄에 걸쳐 각 배달 주문의 위치가 순서대로 한 줄에 하나씩 좌표 (x, y)로 주어지고, 그 다음 M 줄에 걸쳐 각 무상 급식 신청 위치가 한 줄에 하나씩 좌표 (x, y)로 주어진다(0 ≤ x ≤ 100, 0 ≤ y ≤ 100, x, y 는 정수). x 와 y 는 하나의 공백을 사이에 두고 주어진다.

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 한 명의 배달원이 두 종류의 배달을 마칠 수 있는 최단 거리를 출력하시오. 단, 소수점 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.