There are closed intervals . You need to choose intervals such that the intervals have nonempty intersection. In other words, there exists some such that for any selected interval , .

The cost of selecting a collection of intervals with nonempty intersection is the maximum length of the intervals minus the minimum length of the intervals. The length of interval is .

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

.

#### Input Specification

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

In the following lines, each line consists of two integers 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 , , the optimal solution is to choose intervals . is contained in all three intervals. The longest interval is and the shortest interval is , so the cost should be .

#### 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 | |||
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 | |||

17 | |||

18 | |||

19 | |||

20 |

## Comments