나이트 이야기

무한히 큰 체스판이 있다. 이 체스판의 서로 다른 칸에 나이트 $N$개가 놓여 있다. 또한 체스판에는 칸 $N$개가 특별히 표시되어 있으며, 이 칸들을 목적칸이라고 부른다. 모든 목적칸은 어떤 나이트의 처음 위치와도 겹치지 않는다.

나이트 $N$개를 모두 목적칸으로 옮기는 데 필요한 최소 이동 횟수의 합을 구하는 프로그램을 작성하시오. 나이트는 모두 똑같이 생겨서 서로 구분할 수 없으므로, 어떤 나이트가 어떤 목적칸으로 갈지는 자유롭게 정할 수 있다. 여러 나이트가 같은 칸에 동시에 있어도 되지만, 최종적으로 각 목적칸에는 정확히 나이트 한 개씩 놓여 있어야 한다.

나이트는 한쪽으로 두 칸, 그에 수직인 방향으로 한 칸 움직이는 L자 형태로 이동한다. 즉, 칸 $(x, y)$에서 $(x \pm 1, y \pm 2)$ 또는 $(x \pm 2, y \pm 1)$의 여덟 칸 중 하나로 이동할 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 나이트의 수(= 목적칸의 수) $N$이 주어진다. ($1 \le N \le 15$) 이어지는 $N$개의 줄에는 각 나이트의 처음 위치를 나타내는 두 정수 $x$와 $y$가 주어진다. 그다음 $N$개의 줄에는 각 목적칸의 좌표 $x$와 $y$가 주어진다. 모든 좌표는 32비트 부호 있는 정수 범위 안의 값이다.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

k. m

여기서 $k$는 테스트 케이스의 번호(1부터 시작)이고, $m$은 나이트를 모두 목적칸으로 옮기는 최소 이동 횟수의 합이다.