Minimum Cost Interval Selection

Given n closed intervals on the real line numbered from 1 to n, where the i-th interval is \([l_i, r_i]\) and its length is defined as \(r_i - l_i\), you are to choose exactly m intervals such that there exists at least one point \(x\) that lies in every chosen interval. In other words, the chosen intervals must have a non-empty common intersection.

The cost of a valid selection is defined as the difference between the maximum interval length and the minimum interval length in the chosen set. Formally, if the chosen intervals have lengths \(L_1, L_2, \ldots, L_m\) (where \(L_i = r_i - l_i\)), then the cost is

\[\max\{L_i\} - \min\{L_i\}\]

Your task is to find the minimum cost among all valid selections. If no valid selection exists, output \(-1\).

inputFormat

The first line contains two integers n and m (1 ≤ m ≤ n), representing the number of intervals and the number of intervals to choose respectively.

Each of the following n lines contains two integers l_i and r_i (with l_i ≤ r_i), describing the endpoints of the i-th interval.

outputFormat

Output a single integer — the minimum cost among all valid selections. If there is no valid selection, output -1.

sample

3 2
1 3
2 4
3 5

0