날씨가 좋은 어느 6월에 어느날

나무의 기둥에서 새로운 가지가 자라나고 있었다.

그래서 은우는 너무 가지들이 지저분하게 자라는 것을 보고 생각에 잠겼다.

어떻게 하면 깔끔하게 정리가 가능할까 고민하다 가지들을 전부 자르기로 했다.

가지치기를 하려고 하면 나무에서 부터 가지까지 긴 가위가 필요하게 된다.

모든 가지를 다 자르려고 하면 최소 가위의 길이는 얼마가 되어야 하는가?

단, 사용하는 가위는 특이하게 상(위로),하(아래로), 좌(왼쪽),우(오른쪽),대각선(단위 정사각형의 대각선)으로 늘어나는 가위이다.

위의 그림과 같이 나무가 (6,0)에 있고

1번 가지는 (4,2)에 있기 때문에 나무에서 대각선으로 최소 2의 길이만 필요하다.

2번 가지는 (5,5)에 있기 때문에 나무에서 상(위)로 4, 대각선으로 1이 필요하여 총 5의 길이가 필요하다.

3번 가지는 (8,0)이므로 우(오른쪽) 2이므로 최소 2의 길이만 필요하다.

4번 가지는 (3,1)이므로 좌(왼쪽) 2와 대각선 1으로 최소 3이 필요하다

결국 가장 긴 길이가 필요한 2번가지까지 가지치기를 해야 해서 답은 5가 필요하다.

첫줄에 나무의 위치 P(X0,Y0)이 주어진다.

둘째 줄에 가지의 개수를 나타내는 n 이 주어진다. ( 1<=n<=1,000,000 인 자연수)

셋째 줄부터 n개의 줄에 가지의 위치 T(Xi, Yi)가 차례대로 주어진다.

(0<=Xi, Yi<=1,000,000인 정수)

모든 가지치기가 가능한 최소 가위 크기를 출력한다.

admin