KOSTA

Time limit5sMemory limit256 MB

Summary

Place one or two machines on given restaurant sites to minimize the farthest Manhattan delivery distance, and report that distance with the chosen sites.

Level: Medium7 of 10
Topics: Binary search, Geometry
Solved: No attempts yet

Problem

Grill master Kosta opened $N$ restaurants in Manhattan at integer coordinates. The distance between restaurants $A$ and $B$ is $|X_A - X_B| + |Y_A - Y_B|$ . Kosta will install at most $K$ burger machines ( $K$ is $1$ or $2$ ) in existing restaurants and deliver burgers each morning from the nearest machine. For restaurant $C$ , let $D_C$ be the distance to the closest machine. Minimize the maximum $D_C$ . Both machines may be placed in the same restaurant. Output the minimum possible $D$ and the chosen restaurant numbers.

Input

The first line contains $K$ ( $1 \le K \le 2$ ). The second line contains $N$ . Each of the next $N$ lines has coordinates $X$ and $Y$ ( $0 \le X, Y \le 10^6$ ). No two restaurants share a point.

Output

Print the minimum possible $D$ on the first line. On the second line print $K$ restaurant numbers separated by spaces.

Examples3

Example 1
Input
```
2
5
1 1
2 3
5 10
4 6
7 12
```
Expected output
```
5
1 3
```

Example 2

Input

Expected output

5
1 3

Example 3

Input

Expected output

10
3