KOSTA

그릴 장인 Kosta는 Manhattan에 $N$개의 식당을 열었다. 식당 $A$는 정수 좌표 $(X_A, Y_A)$에 있다. 두 식당 사이 거리는 $|X_A - X_B| + |Y_A - Y_B|$다.

Kosta는 자동 버거 기계를 최대 $K$개($K \in \{1, 2\}$) 기존 식당에 설치하고, 나머지 식당에는 매일 아침 가장 가까운 기계가 있는 식당에서 차로 배달한다. 식당 $C$의 $D_C$는 $C$에서 기계가 있는 식당까지의 최단 거리다. 모든 $D_C$의 최댓값을 최소화하는 기계 위치를 고른다. 두 기계를 같은 식당에 설치할 수 있다. 최소 가능한 $D$와 기계를 설치할 식당 번호를 출력한다.

첫 줄에 정수 $K$ ($1 \le K \le 2$)가 주어진다. 둘째 줄에 식당 수 $N$이 주어진다. 다음 $N$줄에 각 식당의 좌표 $X$, $Y$ ($0 \le X, Y \le 10^6$)가 주어진다. 같은 좌표에 두 식당은 없다.

첫 줄에 최소 가능한 $D$를 출력한다. 둘째 줄에 $K$개의 식당 번호를 공백으로 구분해 출력한다.