농부 창호가 농장을 짓고자 한다. 그에게 일하는 소 N(2≤N≤10,000)마리가 있는데, 소 i는 (X_i,Y_i) (-10,000≤X_i,Y_i≤10,000)에서 일한다.

각 소들에 대해서 상하좌우로 인접한 소는 없다.

창호는 이러한 소들을 위해 소들의 일하는 좌표랑 겹치지 않게 농장을 지어야한다. 그리고 각 소들이 농장으로 오는 맨하튼 거리의 합을 최소화 시키면서 농장을 짓고 싶어한다.

(X₁,Y₁)과 (X₂,Y₂)사이의 맨하튼 거리는 다음과 같이 정의된다. |X₁-X₂|+|Y₁-Y₂| 농장은 소들의 일하는 위치와 겹치지 않으면서 각 소들이 농장으로 오는 맨하튼 거리의 합의 최소값과, 최소값이 가능한 좌표의 개수를 구하자.

농장짓기 timer 1s memory - MB

농장짓기 1s - MB