구간 자르기
메모리 제한1024 MB
N개의 구간과 최대 C번의 정수 지점 자르기가 주어질 때, 각 자르기가 X를 엄격히 포함하는 모든 구간을 나눈다는 규칙 아래 얻을 수 있는 구간 수의 최댓값을 구한다.
문제
N개의 구간이 주어진다. 구간은 두 양의 정수 Li와 Ri로 나타낼 수 있으며, Li에서 시작해 Ri에서 끝나는 구간을 [Li,Ri]로 표기한다. 구간이 서로 같을 수 있으므로 Li와 Ri가 모두 같은 구간이 여러 개 있을 수 있다.
최대 C번의 자르기를 할 수 있다. X에서 자르면 L<X이고 X<R인 모든 구간 [L,R]을 자른다. X에서 구간을 자른다는 것은 구간을 [L,X]와 [X,R] 두 구간으로 나누는 것이다. 자르기는 정수 점에서만 할 수 있다. 또한 구간의 끝점(X=L 또는 X=R)에서 자르는 것은 아무 효과가 없으며 구간을 나누지 않는다.
최대 C번의 자르기로 얻을 수 있는 구간의 최대 개수를 구하라.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫째 줄에는 구간의 수 N과 할 수 있는 자르기의 최대 횟수 C가 주어진다. 이어서 N개의 줄이 주어진다.
i번째 줄에는 i번째 구간을 나타내는 두 정수 Li와 Ri가 주어진다.
출력
각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 대로 최대 C번의 자르기로 얻을 수 있는 구간의 최대 개수이다.
제한
- 1 ≤ T ≤ 100.
힌트
주어진 예제에서는 2와 3에서 잘라야 구간의 개수가 최대가 된다.
2에서 처음 자르면 구간은 {[1,2],[2,3],[2,4],[1,2],[2,4]}가 된다.
3에서 두 번째로 자르면 구간은 {[1,2],[2,3],[2,3],[3,4],[1,2],[2,3],[3,4]}가 된다.
더 자를 수 있는 구간이 없으므로 답은 7이다.