Le village KOI possède $N$ maisons sur un plan bidimensionnel. La maison $i$ se trouve en $(X_i,Y_i)$.

La distance entre les maisons $i$ et $j$ est $|X_i-X_j|+|Y_i-Y_j|$, soit la somme des différences de coordonnées $X$ et $Y$. Par exemple, les maisons en $(1,6)$ et $(2,4)$ sont distantes de $(2-1)+(6-4)=3$.

KOI prévoit d’installer des abris dans $K$ maisons pour permettre aux habitants d’évacuer en sécurité en cas de catastrophe. Pour protéger tous les habitants, il faut choisir les $K$ maisons en minimisant la plus grande distance d’une maison à son abri le plus proche, puis déterminer cette distance.

La figure ci-dessous montre un village de $5$ maisons situées en $(1,5),(3,0),(3,3),(6,12),(8,9)$.

On souhaite installer $2$ abris. S’ils sont placés en $(3,0)$ et $(1,5)$, les distances des trois autres maisons à leur abri le plus proche sont respectivement $3,11,12$ ; la plus grande est $12$.

En revanche, avec des abris en $(3,3)$ et $(6,12)$, la maison la plus éloignée de son abri le plus proche est $(8,9)$, à distance $5$ de $(6,12)$. Aucun placement ne donne une distance maximale inférieure à $5$, donc la distance cherchée est $5$.

Étant donnés les emplacements des maisons de KOI et le nombre d’abris, trouvez la plus petite valeur possible de la plus grande distance d’une maison à son abri le plus proche, parmi tous les placements.

Contraintes

• Tous les nombres donnés sont entiers.
• $1 \le K \le 3$
• $K \le N \le 50$
• $0 \le X_i \le 100\,000$
• $0 \le Y_i \le 100\,000$
• Deux maisons n’occupent jamais le même emplacement ; les points $(X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)$ sont distincts.

Sous-tâches

1. ($5$ points) $N=K+1$
2. ($7$ points) $K=1$, pour tout $i$ ($1 \le i \le N$), $X_i=i$ et $Y_i=0$.
3. ($10$ points) $K=1$
4. ($18$ points) $K=2$
5. ($35$ points) $K=3$, pour $1 \le i \le N-1$, $X_i<X_{i+1}$, et pour tout $i$ ($1 \le i \le N$), $Y_i=0$. Ainsi, $X$ est trié par ordre croissant.
6. ($25$ points) $K=3$

Entrée

La première ligne contient $N$ et $K$, séparés par une espace.

Les $N$ lignes suivantes donnent les positions : la ligne $i$ ($1 \le i \le N$) contient $X_i$ et $Y_i$, séparés par une espace.

Sortie

Affichez la réponse sur la première ligne.

Exemples

Entrée 1

5 2
1 5
3 0
3 3
6 12
8 9

Sortie 1

5

Entrée 2

4 2
0 0
0 5
5 0
5 5

Sortie 2

5

Entrée 3

4 1
1 0
2 0
3 0
4 0

Sortie 3

2

Entrée 4

2 1
20 23
5 14

Sortie 4

24