A calibration run collects n sensor readings. For every unordered pair of readings, the drift is the absolute difference of the two values. There are n*(n-1)/2 such drift values (counting multiplicity).
Report the k-th smallest drift (1-indexed) among all pairs. The intended approach binary-searches on the drift value and, for each candidate, counts in linear time (over the sorted readings) how many pairs have drift at most that candidate.
Input format
Line 1: two integers n and k.
Line 2: n space-separated integers, the sensor readings.
Output format
A single integer: the k-th smallest pairwise absolute difference.
Constraints
- 2 <= n <= 40
- 1 <= k <= n*(n-1)/2
- 0 <= each reading <= 1000000000