There are ~n~ closed intervals ~[l_1, r_1], [l_2, r_2], \dots, [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 \le x \le 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.

Input Specification

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 \le m \le 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 Specification

Output a line with an integer denoting the minimum cost.

Sample Input 1

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

Sample Output 1

2

Explanation for Sample 1

When ~n = 6~, ~m = 3~, the optimal solution is to choose intervals ~[3, 5], [3, 4], [1, 4]~. ~4~ is contained in all three intervals. The longest interval is ~[1, 4]~ and the shortest interval is ~[3, 4]~, so the cost should be ~(4-1)-(4-3) = 2~.

Attachment Package

The samples are available here.

Additional Samples

For sample 2: see ex_interval2.in for sample input and ex_interval2.ans for sample output.

For sample 3: see ex_interval3.in for sample input and ex_interval3.ans for sample output.

Constraints

Test case	~n =~	~m=~	~l_i, r_i~
1	~20~	~9~	~0 \le l_i \le r_i \le 100~
2		~10~
3	~199~	~3~	~0 \le l_i \le r_i \le 100\,000~
4	~200~
5	~1\,000~	~2~
6	~2\,000~
7	~199~	~60~	~0 \le l_i \le r_i \le 5\,000~
8	~200~	~50~
9			~0 \le l_i \le r_i \le 10^9~
10	~1\,999~	~500~	~0 \le l_i \le r_i \le 5\,000~
11	~2\,000~	~400~
12		~500~	~0 \le l_i \le r_i \le 10^9~
13	~30\,000~	~2\,000~	~0 \le l_i \le r_i \le 100\,000~
14	~40\,000~	~1\,000~
15	~50\,000~	~15\,000~
16	~100\,000~	~20\,000~
17	~200\,000~		~0 \le l_i \le r_i \le 10^9~
18	~300\,000~	~50\,000~
19	~400\,000~	~90\,000~
20	~500\,000~	~200\,000~