Interval

시간 제한3초메모리 제한1024 MB

요약

n개의 닫힌 구간에서 공통점을 가지는 m개를 골라 선택한 구간 길이의 최댓값과 최솟값의 차이를 최소로 만들고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 정렬, 슬라이딩 윈도우, 구간, 그리디
정답자: 아직 제출이 없습니다

문제

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.

제한

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

예제1

예제 1
입력
```
6 3
3 5
1 2
3 4
2 2
1 5
1 4
```
예상 출력
```
2
```