Cordon Bleu

파리의 한 사업가가 유명한 프랑스 요리 이름을 딴 식당 "Au bon cordon bleu"를 열었다. 그런데 이 요리에 어울리는 와인을 아는 사람이 아무도 없다. 사업가는 와인 목록을 만들려고 여러 와인을 직접 맛보기로 했다.

맛볼 와인은 파리 안팎에 흩어져 있는 여러 와인 상인에게서 가져온다. 고급 와인은 아주 예민한 상품이라 훈련받은 배달원이 오토바이로만 옮길 수 있다. 그래서 배달원 요금이 비싸다.

배달원 한 명이 여러 병을 옮길 수 있지만, 한 번에 한 병만 싣는다. 요금은 모든 배달원이 똑같이 1킬로미터에 1유로다. 거리는 이동 구간마다 맨해튼 거리로 잰다. 즉 점 $(x_1, y_1)$에서 점 $(x_2, y_2)$까지의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

와인 한 병만 옮기는 배달원은 자기 출발 지점에서 와인 상인이 있는 곳까지 간 뒤 식당까지 가고, 두 거리의 합만큼 유로를 받는다.

두 병을 이어서 옮기는 배달원은 출발 지점에서 첫 번째 병이 있는 곳, 식당, 두 번째 병이 있는 곳, 다시 식당 순서로 움직이고, 그 거리의 합만큼 받는다.

사업가를 도와 배달원 고용 비용을 최소로 줄여라. 배달원 출발 지점의 좌표, 와인 병이 놓인 곳의 좌표, 식당의 좌표가 주어질 때 모든 병을 식당으로 모으는 데 드는 최소 이동 거리를 구하라. 배달원을 모두 쓸 필요는 없고, 병을 가져오는 순서도 마음대로 정한다.

입력은 여러 줄로 이루어지고, 각 줄에는 공백 하나로 구분한 정수가 들어 있다.

• 첫째 줄에 모아야 할 와인 병의 수 $N$과 쓸 수 있는 배달원의 수 $M$이 주어진다.
• 다음 $N$개 줄에는 각 와인 병의 좌표 $x$와 $y$가 정수로 주어진다.
• 다음 $M$개 줄에는 각 배달원 출발 지점의 좌표 $x$와 $y$가 정수로 주어진다.
• 마지막 줄에는 식당의 좌표 $x$와 $y$가 주어진다.

제한

• $1 \le N \le 1000$
• $1 \le M \le 1000$
• 모든 좌표는 $-1000 \le x \le 1000$, $-1000 \le y \le 1000$을 만족한다.

모든 병을 모으는 데 지불해야 하는 최소 금액을 정수 하나로 출력한다.

같은 위치에 여러 대상이 놓일 수 있다. 예를 들어 와인 두 병과 배달원 열 명, 식당이 모두 같은 지점에 있어도 된다.

위 그림의 배치에서는 배달원 C2 한 명만 움직여 병 B1과 B2를 식당 R로 가져오고, 1번부터 4번까지 표시한 순서대로 이동한다. 이동 거리의 합은 5이고, 이것이 최적해 중 하나다.