K-th Smallest Pair Distance

Houses stand along a straight road, and homes[i] is the position of house i in metres. For every pair of different houses, measure the distance between them, the absolute difference of their positions. Two houses can stand at the same position, giving a distance of 0.

Write kth_distance(homes, k) that returns the k-th smallest of all these distances, counting from 1 and keeping repeats.

Examples

kth_distance([1, 6, 3], 1)      # returns 2
kth_distance([1, 6, 3], 3)      # returns 5
kth_distance([4, 4, 9, 1], 2)   # returns 3

The three distances of the first two examples are 5, 2 and 3, which sorted are 2, 3, 5. In the last example the six distances sorted are 0, 3, 3, 5, 5, 8.

Constraints

• 2 <= len(homes) <= 20,000
• 0 <= homes[i] <= 10^6
• 1 <= k <= len(homes) * (len(homes) - 1) // 2

Note

20,000 houses make almost 200 million pairs, too many to list and sort.