Description

On the number line, there are $n$ closed intervals numbered from $1$ to $n$. The $i$-th closed interval is $[l_i, r_i]$.

Now we need to choose $m$ intervals such that these $m$ intervals share at least one position. In other words, there exists an $x$ such that for every selected interval $[l_i, r_i]$, we have $l_i \leq x \leq r_i$.

For a valid selection, its cost is the length of the longest selected interval minus the length of the shortest selected interval.

The length of an interval $[l_i, r_i]$ is defined as $(r_i - l_i)$, i.e., the value of the right endpoint minus the value of the left endpoint.

Find the minimum cost among all valid selections. If no valid selection exists, output $-1$.

Input Format

The first line contains two integers, representing $n$ and $m$.

From line $2$ to line $(n + 1)$, each line contains two integers representing an interval. On line $(i + 1)$, the integers $l_i, r_i$ denote the left and right endpoints of the $i$-th interval.

Output Format

Output a single integer on one line representing the answer.

6 3
3 5
1 2
3 4
2 2
1 5
1 4

2

Hint

Explanation for Sample Input/Output 1

As shown, when $n = 6$, $m = 3$, the minimum-cost plan is to select the three intervals $[3, 5], [3, 4], [1, 4]$. They all contain position $4$, so the selection is valid. Among them, the longest interval is $[1, 4]$, and the shortest interval is $[3, 4]$, so the cost is $(4 - 1) - (4 - 3) = 2$.

Constraints and Conventions

::cute-table{tuack}

There are 20 test points in total. See the table below for details. | Test point ID | $n=$ | $m=$ | $l_i, r_i$ | |:-:|:-:|:-:|:-:| | 1 | $20$ | $9$ | $0 \le l_i \le r_i \le 100$ | | 2 | ^ | $10$ | $0 \le l_i \le r_i \le 100$ | | 3 | $199$ | $3$ | $0 \le l_i \le r_i \le 100000$ | | 4 | $200$ | ^ | ^ | | 5 | $1000$ | $2$ | ^ | | 6 | $2000$ | ^ | ^ | | 7 | $199$ | $60$ | $0 \le l_i \le r_i \le 5000$ | | 8 | $200$ | $50$ | ^ | | 9 | ^ | ^ | $0 \le l_i \le r_i \le 10^9$ | | 10 | $1999$ | $500$ | $0 \le l_i \le r_i \le 5000$ | | 11 | $2000$ | $400$ | ^ | | 12 | ^ | $500$ | $0 \le l_i \le r_i \le 10^9$ | | 13 | $30000$ | $2000$ | $0 \le l_i \le r_i \le 100000$ | | 14 | $40000$ | $1000$ | ^ | | 15 | $50000$ | $15000$ | ^ | | 16 | $100000$ | $20000$ | ^ | | 17 | $200000$ | ^ | $0 \le l_i \le r_i \le 10^9$ | | 18 | $300000$ | $50000$ | ^ | | 19 | $400000$ | $90000$ | ^ | | 20 | $500000$ | $200000$ | ^ |

For all test points, it is guaranteed that $1 \le m \le n$, $1 \le n \le 5 \times 10^5$, $1 \le m \le 2 \times 10^5$, $0 \le l_i \le r_i \le 10^9$.

Translated by ChatGPT 5