这个问题的两个版本之间的唯一区别是 $$$k$$$ 的约束、时间限制和内存限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Doremy 生活在一个多雨的国家,由 $$$n$$$ 个城市组成,编号从 $$$1$$$ 到 $$$n$$$。
天气预报预测了未来 $$$m$$$ 天的降雨分布。第$$$i$$$天,$$$[l_i, r_i]$$$区间内的城市将下雨。如果一个城市在接下来的 $$$m$$$ 天内永远不会下雨,则该城市被称为干燥城市。
原来多蕾米拥有一种特殊的力量。她可以选择 $$$k$$$ 天,这些天不会下雨。多雷米想要计算出使用特殊力量后最多能有多少个干旱城市。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$2 \le k \le \min(10, m)$$$) — 城市数量,天数,以及 Doremy 可以阻止的下雨天数。
然后,接下来是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — $$$i$$$ 天的降雨覆盖范围。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——干旱城市的最大数量。
示例
输入 #1
6 2 3 2 1 2 1 2 1 1 5 3 2 1 3 2 4 3 5 10 6 4 1 5 6 10 2 2 3 7 5 8 1 4 100 6 5 1 100 1 100 1 100 1 100 1 100 1 100 1000 2 2 1 1 1 1 20 5 3 9 20 3 3 10 11 11 13 6 18
输出 #1
1 2 6 0 1000 17
注意
在第一个测试用例中,如果 Doremy 阻止
- 下雨$$$1,2$$$,然后城市$$$2$$$将会干燥;
- 下雨$$$2,3$$$,那么没有城市会干燥;
- 下雨$$$1,3$$$,那么没有城市会干燥;
所以最多有 $$$1$$$ 干燥城市。
在第二个测试用例中,如果 Doremy 阻止
- 下雨$$$1,2$$$,然后城市$$$1,2$$$将会干燥;
- 下雨$$$2,3$$$,然后城市$$$4,5$$$将会干燥;
- 下雨$$$1,3$$$,然后城市$$$1,5$$$将会干燥。
所以最多有 $$$2$$$ 干旱城市。
在第三个测试用例中,最好防止下雨$$$1,2,4,5$$$。
在第四个测试用例中,总有那么一天,雨水打湿了所有的城市,无法避免。