25743번 - Interval 다국어

There are $n$ closed intervals $[l_1,r_1], [l_2,r_2], \ldots, [l_n,r_n]$. You need to choose $m$ intervals such that the $m$ intervals have nonempty intersection. In other words, there exists some $x$ such that for any selected interval $[l_i,r_i]$, $l_i \leq x \leq r_i$.

The cost of selecting a collection of $m$ intervals with nonempty intersection is the maximum length of the $m$ intervals minus the minimum length of the $m$ intervals. The length of interval $[l_i, r_i]$ is $r_i - l_i$.

Compute the minimum cost of choosing $m$ intervals with nonempty intersection. If this is impossible, output -1.

The first line consists of two positive integers $n,m$ separated by a single space where $n$ is the total number of intervals and $m$ is the number of intervals we are going to choose. It is guaranteed that $1 \leq m \leq n$.

In the following $n$ lines, each line consists of two integers $l_i,r_i$ separated by a space denoting the left and right endpoints of an interval.

Output a line with an integer denoting the minimum cost.

See ex_interval2.in for sample input and ex_interval2.ans for sample output.

See ex_interval3.in for sample input and ex_interval3.ans for sample output.