울타리

어느 아침, 과수원 주인 Fred가 사과나무를 둘러보다가 밤사이에 나무 한 그루가 베어졌다는 것을 알게 되었다. 나무 한 그루는 평균적으로 111€의 가치를 가진다. 이는 그 나무의 사과로 벌 수 있는 금액이다. 더 이상의 손실을 막기 위해 Fred는 과수원에 울타리를 세우기로 했다.

울타리는 철사로 연결된 기둥으로 이루어진다. 기둥은 미리 뚫려 있는 구멍들 중에만 세울 수 있다. 철사는 공짜지만 기둥은 한 개당 20€에 사야 하므로, 모든 나무를 둘러싸는 것이 항상 이득이거나 가능한 것은 아니다.

과수원은 1000×1000 m² 크기의 정사각형이다. 위에서 내려다볼 때 왼쪽 아래 모서리가 (0, 0), 오른쪽 위 모서리가 (1000, 1000)이다.

예를 들어, 미리 뚫린 구멍이 네 개(원), 나무가 세 그루(사각형) 있다고 하자. 최선의 선택은 기둥 세 개를 사서 선택된 구멍(가 채워진 원)에 세우고 철사(선)로 연결한 뒤, 왼쪽 위 구멍은 비워 두는 것이다. 이때 비용은 3·20€ + 1·111€ = 171€가 된다. 기둥 세 개를 샀고 나무 한 그루를 둘러싸지 못했기 때문이다(그 나무의 수확량 손실).

미리 뚫린 구멍들과 나무들의 위치를 입력받아, 울타리를 전혀 세우지 않는 것까지 포함해 최소 총비용을 출력하는 프로그램을 작성하라. 각 나무는 하나의 점으로 보고, 실제 모양은 무시한다.

첫 줄에 두 정수 N과 M이 주어진다 (3 ≤ N ≤ 100, 1 ≤ M ≤ 100). N은 미리 뚫린 구멍의 수, M은 나무의 수이다. 다음 N개 줄에는 구멍의 위치가, 그 다음 M개 줄에는 나무의 위치가 주어진다. 각 위치는 한 줄에 두 정수 x y로 주어진다 (0 ≤ x, y ≤ 1000). 서로 같은 위치는 없으며, 세 위치가 한 직선 위에 놓이는 경우도 없다.

Fred의 최소 비용을 한 줄에 정수 하나로 출력한다. Fred가 기둥 P개를 사고 나무 T그루를 둘러싸지 못했다면, 비용은 20·P + 111·T이다.