問題文

ユークリッド平面上に、N 個の点 (X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N) があります。 これらを、次の条件を満たすように K 個のグループに分けることを考えます。

• 複数のグループに入る点があってはならない。
• どのグループにも属さない点があってはならない。
• ひとつも点が属さないグループがあってはならない。

このとき、同一グループ内での 2 点間距離の最大値を最小化してください。 ただし、ジャッジにはこのときの同一グループ内での 2 点間距離の最大値の 2 乗を 出力してください。

なお、このときの最大値を 2 乗した値は必ず整数になることが証明できます。

制約

• 2\leq K< N\leq 15
• 0\leq X_i,Y_i\leq 10^9
• (X_i,Y_i)\neq (X_j,Y_j) (i\neq j)
• 入力は全て整数

入力例 1

3 2
0 1
1 2
2 0

出力例 1

2

\{(0,1),(1,2)\}, \{(2,0)\} となるように分けると、同一グループ内での 2 点間距離の最大値は \sqrt 2 になってこれが最小なので、これを 2 乗した 2 を出力します。

入力例 2

5 3
0 0
1 1
0 2
2 3
3 1

出力例 2

4

\{(0,0),(0,2)\}, \{(1,1),(3,1)\}, \{(2,3)\} と分けると、距離の最大値が 2 の組が二つできて、その最大値は 2 です。

\{(0,0)\}, \{(0,2),(1,1)\}, \{(2,3),(3,1)\} などと分けることもできますが、この場合同一グループ内の 2 点間距離は \sqrt2 と \sqrt5 となります。

入力例 3

10 4
0 3
3 5
2 7
9 0
5 6
4 3
7 8
6 5
9 9
2 1

出力例 3

20

入力例 4

3 2
0 0
500000000 500000000
1000000000 1000000000

出力例 4

500000000000000000