문제

비행기 조종사 형석이는 최근 여객용 경비행기를 하나 사들였다. 여객기를 사들이게 된 것에는 여러가지 이유가 있지만 돈을 벌기 위해서였다. 형석이의 경비행기는 조종사 포함 두 명이 탈 수 있으므로 손님은 한 명만 탈 수 있다. 그리고 형석이의 경비행기가 운행할 지역을 2차원 평면으로 취급하려고 한다. 각 지역의 좌표는 $(x,y)$로 나타낼 수 있다고 한다.

형석이의 경비행기는 비행할 때마다 정비 등의 작업을 해야하기 때문에, 적어도 3시간의 시간 간격을 확보하려고 한다. 예를 들어 오전 1시에 착륙을 했다고 해보자. 그러면 다음 비행 일정은 같은 날 오전 4시 또는 그 이후에 착륙하게 하려 한다. 형석이의 경비행기는 성능이 좋기 때문에 비행 시간은 무시할 수 있을 정도로 짧다.

또 다음과 같은 방식으로 손님에게 돈을 받기로 결정했다. $(x_1, y_1)$에서 $(x_2, y_2)$로 비행을 하는 경우, $\max(|x_1 - x_2|, |y_1 - y_2|)$를 기본 운임으로 한다. 즉, 출발지와 목적지의 Chebyshev 거리($\mathrm{L}_{\infty}$ metric, maximum metric)에 해당하는 금액을 받기로 한 것이다. 그리고 연료비, 정비료 등 비행하기 위해 필요한 추가 금액은 손님 부담으로 하기로 결정했다.

형석이는 착륙이 가능한 지점들을 모두 조사하였다. 착륙이 가능한 지점이라고 해도 항상 착륙이 가능하지는 않았고, 특정한 시각에만 착륙할 수 있었다. 그 특정한 시각이 지나면 착륙할 수 없고, 정확히 특정한 시각에만 도착해야 했다. 게다가 착륙을 하는 데에도 비용이 들었고 지점마다 비용이 달랐다. 그래서 착륙이 가능한 지점의 위치, 시각, 비용을 모두 조사하였다. 착륙하는 데 필요한 비용마저 손님에게 부담시키는 것은 하기 싫었기 때문에 착륙하는 데 필요한 비용은 형석이가 내기로 결심했다.

조사한 정보를 바탕으로 형석이는 자신의 집 $(0, 0)$에서 경비행기 운영을 시작하려고 한다. 형석이와 함께 경비행기를 타고 싶어하는 사람은 매우 많기 때문에, 경비행기가 뜨기만 하면 항상 손님을 태우고 이동할 수 있다고 한다. 형석이가 가장 많은 돈을 벌기 위해 최선의 방법으로 경비행기를 운영한다면, 마지막 착륙 이후 얻을 수 있는 최대 금액은 얼마인지 계산해야 한다. 만약 어떤 방법을 써도 비행하는 것이 손해라면 형석이는 아예 비행을 포기할 수도 있고 이 때 얻을 수 있는 최대 금액은 0이다.