## NOI '16 P4 - Interval

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

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.

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.

Test case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20