구간 자르기

$\mathbf{N}$개의 구간이 주어진다. 구간은 두 양의 정수 $\mathbf{L_i}$과 $\mathbf{R_i}$로 나타낼 수 있다. 구간은 $\mathbf{L_i}$에서 시작하여 $\mathbf{R_i}$에서 끝나며, $[\mathbf{L_i}, \mathbf{R_i}]$로 나타낸다. 구간들은 서로 다르지 않을 수 있으므로, $\mathbf{L_i}$이 같고 $\mathbf{R_i}$도 같은 구간이 여러 개 있을 수 있다.

최대 $\mathbf{C}$번 자를 수 있다. $X$에서 자르면, $L \lt X$이고 $X \lt R$인 모든 구간 $[L, R]$가 잘린다. $X$에서 구간을 자른다는 것은 그 구간을 $[L, X]$와 $[X, R]$의 두 구간으로 나누는 것으로 정의한다. 자르기는 정수 지점에서만 수행할 수 있음에 유의하라. 또한 구간의 끝점($X = L$ 또는 $X = R$)에서 자르는 것은 아무 효과가 없으며 구간을 나누지 않는다.

최대 $\mathbf{C}$번의 자르기를 통해 얻을 수 있는 구간 수의 최댓값을 구해야 한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 500$. $1 \le \mathbf{C} \le 10^{5}$. 모든 $i$에 대해 $1 \le \mathbf{L_i} \lt \mathbf{R_i} \le 10^{4}$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{C} \le 10^{18}$. 모든 $i$에 대해 $1 \le \mathbf{L_i} \lt \mathbf{R_i} \le 10^{13}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 정수 $\mathbf{N}$과 $\mathbf{C}$가 포함된 줄로 시작하며, 각각 구간의 수와 수행할 수 있는 자르기 횟수의 최댓값을 나타낸다. 이어서 $\mathbf{N}$개의 줄이 주어진다. $i$번째 줄에는 두 정수 $\mathbf{L_i}$과 $\mathbf{R_i}$가 주어지며, $i$번째 구간을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$은 위에서 설명한 대로 최대 $\mathbf{C}$번의 자르기를 통해 얻을 수 있는 구간 수의 최댓값이다.

주어진 예제에서는 구간 수를 최대로 만들기 위해 $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$이다.