#abc075d. [abc075_d]Axis-Parallel Rectangle

[abc075_d]Axis-Parallel Rectangle

問題文

2次元座標上に NN 個の点があります。
i(1iN)i(1≦i≦N) 番目の点の座標は (xi,yi)(x_i,y_i) です。
長方形の内部に NN 点のうち KK 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。

制約

  • 2KN502≦K≦N≦50
  • \-109xi,yi109(1iN)\-10^9≦x_i,y_i≦10^9 (1≦i≦N)
  • xixj(1i<jN)x_i≠x_j (1≦i<j≦N)
  • yiyj(1i<jN)y_i≠y_j (1≦i<j≦N)
  • 入力値はすべて整数である。(21:50 追記)

入力

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

NN KK
x1x_1 y1y_1 ::
xNx_{N} yNy_{N}

出力

条件を満たす長方形の中で最小面積となるような長方形の面積を出力せよ。


入力例 1

4 4
1 4
3 3
6 2
8 1

出力例 1

21

条件を満たす最小面積となる長方形の 11 つは (1,1),(8,1),(1,4),(8,4)(1,1),(8,1),(1,4),(8,4)44 つの頂点で構成されます。
その面積は (81)×(41)=21(8-1) × (4-1) = 21 であるため、2121 と出力します。


入力例 2

4 2
0 0
1 1
2 2
3 3

出力例 2


入力例 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

出力例 3

3999999996000000001

オーバーフローに注意してください。