点の削除

イヅア大学は今年もプログラミングコンテストを開催する。問題作成チームの一員であるあなたは、座標平面上に十分に散らばった複数の点を配置した入力データを生成する必要がある。ところが、実際に生成してみると、点の集まりが十分に散らばらないことがあった。あなたは、生成した点の集まりが十分に散らばるように入力データを修正することにした。

点の集まりの中で最も距離が近い二点間の距離を、その点の集まりの散らばり方の尺度とする。あなたは、点の集まりからいくつかの点を削除することで、この尺度を最大にしたい。

座標平面上の各点の座標と削除する点の数$K$が与えられたとき、点を$K$個削除したときの散らばり方の尺度の最大値の二乗を出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $K$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_N$ $y_N$

１行目に座標平面上の点の数$N$ ($3 \leq N \leq 1,000$)と整数$K$ ($0 \leq K \leq N - 2$ かつ $K \leq 30$)が与えられる。続く$N$行に、点の座標$x_i,y_i$ ($0 \leq x_i,y_i \leq 10,000$)が整数で与えられる。ただし、同じ座標をもつ点は与えられない($i \ne j$について、$x_i \ne x_j$または$y_i \ne y_j$）。

出力

散らばり方の尺度の最大値の二乗を整数で1行に出力する。

入出力例

入力例

5 2
0 0
2 2
4 1
4 2
7 0

出力例

13

Note

Algorithm

 

---