호동이는 자신이 만든 케익을 고객들에게 직접배달을 하려고 한다. N명의 고객에게 케익을 배달하는데 주문이 들어온 순서대로 배달하기를 원하며

고객이 케익을 받을 수 있을 만큼 충분히 가까이까지 배달한다.

N명의 고객의 위치는 순서대로 100 x 100 격자의 정수좌표로 주어지고 처음 출발하는 위치도 정수좌표로 주어진다.

호동이는 격자위에서 상, 하, 좌, 우로만 움직이며

고객에게 케익을 전달하기 위해서는 그 고객의 위치까지 가거나 고객의 상, 하, 좌, 우의 인접격자점에 가야한다.

이때 호동이가 최단 거리를 이동하여 배달을 끝낼 수 있는 거리를 계산하는 프로그램을 작성하시오.

여기서 거리는 격자상의 칸 수를 말한다.

위의 예에서 호동이는 11칸을 움직여서 세명의 고객에게 배달을 다 할 수 있다.

호동이는 반드시 고객들에게 순서대로 배달을 하며

순서에 어긋난 사람에게 배달을 할 수 있는 위치에 있더라도 케익을 주지 않고 순서대로 배달을 한다.

고객의 위치는 중복이 될 수도 있다

케익배달 timer 1s memory 64MB

케익배달 1s 64MB