정올시에 어떤 대규모 박람회가 개최가 결정되었다.

이번 박람회에는 2개의 테마가 있고, 정올시에 있는 N개의 전시시설에서 각각 2개의 테마중에 하나를 골라 전시할 예정이다.

시설의 위치는 평면좌표 (x, y)로 표현한다.

위치 (x, y)에 있는 시설에서 (x', y')에 있는 시설까지 이동하는데는, |x-x'|+|y-y'|만큼의 시간이 걸린다. (정수 a에 대해서, |a|는 절대값을 의미한다.)

동일 테마의 전시내에서 통일감을 내고, 한쪽의 테마만 관심을 가진 사람들이 불편하지 않도록 같은 테마를 전시하는 시설사이의 이동거리를 가능한한 짧게 나누려고 한다.

전시를 나누는 방법은 모든 전시의 테마를 같게 하는 것을 제외하고 모든 경우가 가능하다. 같은 테마를 가지는 전시하는 2개의 시설간의 이동시간의 최대를 M이라한다.

N개의 전시시설이 위치를 나타내었을때 전시들의 테마를 알맞게 나눴을 경우 M의 값이 최소값을 구하는 프로그램을 작성해라.

#2339 upload 57 done 9 how_to_reg 9

박람회 timer 1s memory - MB

#2339

박람회 1s - MB