TopCoder

Thumb c1c8af6a6ee436c5994d03cb1a44b7da
$nA-NIl$
$After$ $Four$ $Years !$

User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

35.1% (26/74)

Tags

Description


傳說中, 在高天原上有一個樹朋友聚落,
這個聚落的樹朋友們很喜歡爬到別人的樹頂上,
當然, 他們也都很樂意讓別人爬到自家樹頂上.

然而隨著時間過去, 許多長得快的樹漸漸與其它樹拉開距離,
這使得樹朋友們要爬到這些樹頂上變得困難.

為此, 樹朋友們決定合力建造一個梯子來輔助爬樹.
對於某個樹對, 如果兩棵樹的高度差小於等於梯子長度, 則梯子就適用於這個樹對.
但因為高天原的樹朋友們非常有環保概念,
他們知道, 如果要讓梯子能夠適用於任兩個樹對, 必定會消耗掉太多資源.
所以他們決定, 這個梯子只需要能夠適用於 k 對樹對即可.

但, 這時問題就來了, 由於樹實在太多,
他們不知道如果要適用於 k 對樹對, 梯子至少要造到多長才行.
而碰巧他們得知了你會寫程式, 所以便求助於你.

你能夠幫助他們找出梯子至少要多長嗎?

Input Format

第一行有兩個數字 n, k. n 代表有幾棵樹.
第二行有 n 個數字, 代表每棵樹的高度.
(1 <= 每棵樹的高度 <= 2 * 109)
(2 <= n <= 200000, 1 <= k <= C(n, 2))

你可以假設每棵樹高度不同.

Output Format

請輸出一個整數代表梯子至少要多長.

Sample Input

5 2
9 18 27 28 37

Sample Output

9

Hints

9雖然適用於4個樹對,
但8以下只能適用於1個樹對, 故選9.

另外, 梯子明明就是拿來從樹頂爬到另一個樹頂的,
為什麼在原圖中卻是從地面爬上去呢?
其實也是因為出題者畫完才發現, 所以也算了(?)

Problem Source

原TIOJ1632 / Problem Setter: worm

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5