Description

瓜瓜在被施巨砲補完牙齒後又遇到了難題。
他覺得自己的牙齒很亂,排列的參差不齊,造成牙齒之間的牙縫有大有小。瓜瓜有 N 顆牙齒,第 i 顆牙齒的座標可以用 (xi,yi) 來表示。
特別的是,瓜瓜的牙縫為三顆牙齒圍成的三角形,所以牙縫的大小即為該三角形的面積的兩倍。在經過施巨砲的觀察之後,他發現為了評估瓜瓜的牙齒必須先知道第 k 小的牙縫大小為多少,你能夠找出這個值並再次拯救瓜瓜的牙齒嗎?

Input Format

第一行有兩個正整數 N,k ,意義如題目所述
接下來的 N 行每行有兩個正整數 xi,yi ,意義如題目所述
測資保證沒有三點共線

對於所有測試資料:

  • 3N800
  • 1k(N3)
  • |xi|,|yi|106

Output Format

輸出第 k 小的牙縫大小。

Sample Input 1

4 3
0 0
-1 -1
1 2
3 1

Sample Output 1

5

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 n200 33
3 0~25 無特別限制 67

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3
1 3000 262144 65536 2 3
2 3000 262144 65536 2 3
3 3000 262144 65536 2 3
4 3000 262144 65536 2 3
5 3000 262144 65536 2 3
6 3000 262144 65536 3
7 3000 262144 65536 3
8 3000 262144 65536 3
9 3000 262144 65536 3
10 3000 262144 65536 3
11 3000 262144 65536 3
12 3000 262144 65536 3
13 3000 262144 65536 3
14 3000 262144 65536 3
15 3000 262144 65536 3
16 3000 262144 65536 3
17 3000 262144 65536 3
18 3000 262144 65536 3
19 3000 262144 65536 3
20 3000 262144 65536 3
21 3000 262144 65536 3
22 3000 262144 65536 3
23 3000 262144 65536 3
24 3000 262144 65536 3
25 3000 262144 65536 3