기지 방어
면접 대비시간 제한8초메모리 제한512 MB
위치와 속도가 주어진 병력과 기지들이 있을 때, 모든 기지에 최소 한 명이 도달하는 최소 시간을 구하거나 불가능하면 그 사실을 출력한다.
문제
국가 기제봄(Gizevom)이 적의 기습적이고 맹렬한 공격을 받고 있다. 나라는 모든 기지에 즉시 하나 이상의 병력을 배치해 방어해야 한다. 그렇지 않으면 적이 모든 기지를 점령하고 "All your base are belong to us"를 선언할 것이다.
병력의 현재 위치와 행군 속도, 기지의 위치가 주어질 때, 배치에 필요한 최소 시간을 계산하는 프로그램을 작성하시오.
입력
입력은 여러 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다:
N M
x1 y1 v1
x2 y2 v2
...
xN yN vN
x'1 y'1
x'2 y'2
...
x'M y'M
N은 병력의 수 (1 ≤ N ≤ 100), M은 기지의 수 (1 ≤ M ≤ 100)이다. (xi, yi )는 i번째 병력의 현재 위치, vi는 i번째 병력의 속도 (1 ≤ vi ≤ 100), (x'j, y'j)는 j번째 기지의 위치이다.
모든 좌표는 0 이상 10000 이하의 정수이다.
마지막 데이터셋 뒤에는 두 개의 0이 있는 줄이 온다. 이 줄은 어떤 데이터셋의 일부도 아니며 처리해서는 안 된다.
출력
각 데이터셋마다 필요한 최소 시간을 한 줄에 출력하시오.