맥베스

시간 제한2초메모리 제한512 MB

요약

n개의 시간 구간과 w명의 마녀가 주어질 때, 각 마녀가 겹치지 않는 구간들의 연쇄를 예측한다고 하면 w개의 연쇄로 덮을 수 있는 구간의 최대 개수를 구한다.

난이도: 보통10점 중 6점
유형: 구간, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

맥베스는 왕에게 충성하는 신하였고, 방금 끝난 전투에서 큰 공을 세웠다. 그런데 그는 세 마녀를 만난다. 마녀들은 그가 곧 승진하고 그 뒤에 왕이 된다고 예언한다. 예언대로 승진이 이루어지자 맥베스는 자기가 왕이 될 운명이라고 믿기 시작한다. 그와 아내는 야망에 눈이 멀어 왕을 죽이고, 위협이나 경쟁자로 보이는 사람을 거의 모두 죽인다.

마녀들이 맥베스를 그렇게까지 흔들 수 있었던 것은 미래를 정확히 맞혔기 때문이다. 맥베스가 예언을 하나만 요구하지 않고 여러 개를 요구했다면 마녀들의 일은 훨씬 어려워졌을 것이다. 수정 구슬로 예언하는 작업은 만만치 않다. 구슬은 어떤 사건을 언제 예언하게 해 줄지 까다롭게 굴고, 예언마다 걸리는 시간도 다르다. 그래서 마녀들이 힘을 합쳐 가장 많은 예언을 하는 방법을 찾는 일은 어려운 문제가 된다.

각 사건에는 시간 구간이 하나씩 딸려 있다. 사건 $i$ 를 예언하려면 마녀 한 명이 구간 $[s_i, t_i]$ 전체 동안 수정 구슬을 들여다보며 오직 사건 $i$ 만 생각해야 한다. 그래서 두 사건의 구간이 같더라도 한 마녀는 그중 하나만 예언할 수 있다. 사건 $i$ 를 예언한 마녀가 이어서 사건 $j$ 를 예언하려면 $t_i \le s_j$ 여야 한다. 마녀들은 서로 맞춰 가며 예언하는 사건의 총 개수를 최대로 만든다.

마녀가 $w$ 명일 때 예언할 수 있는 사건 수의 최댓값을 구하라.

입력

첫 줄에 데이터 집합의 개수 $K \ge 1$ 이 주어진다. 이어서 $K$ 개의 데이터 집합이 아래 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $n$ 과 $w$ 가 주어진다. $0 \le n \le 1000$ 은 사건의 수이고, $1 \le w \le 10$ 은 마녀의 수이다.

다음 $n$ 개의 줄에는 사건 하나를 나타내는 두 정수 $s_i$ 와 $t_i$ 가 주어진다( $0 \le s_i < t_i \le 10^7$ ).

출력

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$ 는 데이터 집합의 번호이고 1부터 센다. 다음 줄에는 마녀들이 예언할 수 있는 사건 수의 최댓값을 출력한다.

각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.

예제6

예제 1

입력

예상 출력

Data Set 1:
5

예제 2
입력
```
1
0 5
```
예상 출력
```
Data Set 1:
0
```
예제 3
입력
```
1
1 1
0 10000000
```
예상 출력
```
Data Set 1:
1
```
예제 4
입력
```
1
3 1
0 5
5 10
10 15
```
예상 출력
```
Data Set 1:
3
```

예제 5

입력

예상 출력

Data Set 1:
3

예제 6

입력

예상 출력

Data Set 1:
1

Data Set 2:
2

Data Set 3:
2