CF1889C2.Doremy's Drying Plan (Hard Version)

The only differences between the two versions of this problem are the constraint on $k$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $n$ cities numbered from $1$ to $n$.

The weather broadcast predicted the distribution of rain in the next $m$ days. In the $i$-th day, it will rain in the cities in the interval $[l_i, r_i]$. A city is called dry if it will never rain in that city in the next $m$ days.

It turns out that Doremy has a special power. She can choose $k$ days, and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

该问题的两个版本之间唯一的区别在于 $k$ 的约束条件、时间限制和内存限制。只有当该问题的两个版本均被解决后，才允许进行 Hack。

Doremy 生活在一个多雨的国家，该国由编号从 $1$ 到 $n$ 的 $n$ 座城市组成。

天气预报预测了接下来 $m$ 天的降雨分布情况。在第 $i$ 天，区间 $[l_i, r_i]$ 内的城市将降雨。若一座城市在接下来的 $m$ 天内始终不会降雨，则称其为“干燥城市”。

事实上，Doremy 拥有一种特殊能力：她可以选择 $k$ 天，在这些天里不会下雨。Doremy 希望计算使用该特殊能力后所能达到的干燥城市的最大数量。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $n$, $m$ and $k$ ($1\le n\le 2\cdot 10^5$, $2 \le m \le 2\cdot 10^5$, $2 \le k \le \min(10, m)$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $m$ lines follow. The $i$-th line contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — the rain coverage on day $i$.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output one integer — the maximum number of dry cities.

对于每个测试用例，输出一个整数——即干燥城市的最大数量。

In the first test case, if Doremy prevents

• rain $1,2$, then city $2$ will be dry;
• rain $2,3$, then no city will be dry;
• rain $1,3$, then no city will be dry;

So there is at most $1$ dry city.

In the second test case, if Doremy prevents

• rain $1,2$, then city $1,2$ will be dry;
• rain $2,3$, then city $4,5$ will be dry;
• rain $1,3$, then city $1,5$ will be dry.

So there are at most $2$ dry cities.

In the third test case, it is optimal to prevent rain $1,2,4,5$.

In the forth test case, there is always a day of rain that wets all the cities and cannot be prevented.

在第一个测试用例中，若 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$。

在第四个测试用例中，总存在某一天的降雨会淋湿所有城市，且该场雨无法被阻止。