P16850 [GKS 2021 #D] Cutting Intervals

You are given $N$ intervals. An interval can be represented by $2$ positive integers $L_i$ and $R_i$ - the interval starts at $L_i$ and ends at $R_i$, represented as $[L_i, R_i]$. Intervals may not be unique, so there might be multiple intervals with both equal $L_i$ and equal $R_i$. You are allowed to perform a maximum of $C$ cuts. A cut at $X$ will cut all intervals $[L, R]$ for which $L < X$ and $X < R$. Cutting an interval at $X$ is defined as splitting the interval into $2$ intervals - $[L, X]$ and $[X, R]$. Note that cuts can only be performed at integer points. Also, cutting at an endpoint of an interval ($X = L$ or $X = R$) has no effect and does not split the interval. You need to find the maximum number of intervals that can be obtained through a maximum of $C$ cuts.

The first line of the input contains the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing $2$ integers, $N$ and $C$, denoting the number of intervals and the maximum number of cuts you can perform respectively. $N$ lines follow. The $i$-th line contains $2$ integers, $L_i$ and $R_i$, describing the $i$-th interval.

For each test case, output one line containing Case $\#x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the maximum number of intervals that can be obtained through at most $C$ cuts, as described above.

In the provided sample, cuts should be performed at $2$ and $3$ to get the maximum number of intervals. After the first cut at $2$, the intervals would be $\{[1, 2], [2, 3], [2, 4], [1, 2], [2, 4]\}$. After the second cut at $3$, the intervals would be $\{[1, 2], [2, 3], [2, 3], [3, 4], [1, 2], [2, 3], [3, 4]\}$. It can be seen that no interval can be cut further, so the answer is $7$. ### Limits Memory limit: $1$ GB. $1 \le T \le 100$. **Test Set $1$** $1 \le N \le 500$. $1 \le C \le 10^5$. $1 \le L_i < R_i \le 10^4$ for all $i$. **Test Set $2$** $1 \le N \le 10^5$. $1 \le C \le 10^{18}$. $1 \le L_i < R_i \le 10^{13}$ for all $i$.