310807: CF1890E2. Doremy's Drying Plan (Hard Version)

E2. Doremy's Drying Plan (Hard Version)time limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

1
2
6
0
1000
17

Note

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）居住在一个有n个城市（编号从1到n）的雨天国家。天气预报预测了接下来m天的降雨分布。在第i天，区间[l_i, r_i]内的城市将会下雨。如果一个城市在接下来的m天内永远不会下雨，则称为干燥城市。多雷米有一个特殊能力，她可以选择k天，在这几天内不会下雨。多雷米想要计算使用特殊能力后，干燥城市的最大数量。

输入数据格式：
输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含三个整数n、m和k（1≤n≤2×10^5，2≤m≤2×10^5，2≤k≤min(10, m)）——城市的数量、天数和Doremy可以阻止的雨天数量。
然后是m行，第i行包含两个整数l_i、r_i（1≤l_i≤r_i≤n）——第i天的降雨范围。
保证所有测试用例的n和m的总和不超过2×10^5。

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

示例：
输入：
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
2
6
0
1000
17

注意：
在第一个测试用例中，如果多雷米阻止1,2天的雨，那么城市2将变干；如果阻止2,3天的雨，那么没有城市会变干；如果阻止1,3天的雨，那么没有城市会变干。因此，最多有1个干燥城市。
在第二个测试用例中，如果多雷米阻止1,2天的雨，那么城市1,2将变干；如果阻止2,3天的雨，那么城市4,5将变干；如果阻止1,3天的雨，那么城市1,5将变干。因此，最多有2个干燥城市。
在第三个测试用例中，最优的做法是阻止1,2,4,5天的雨。
在第四个测试用例中，总有一天会下雨，淋湿所有城市，无法阻止。题目大意： 多雷米（Doremy）居住在一个有n个城市（编号从1到n）的雨天国家。天气预报预测了接下来m天的降雨分布。在第i天，区间[l_i, r_i]内的城市将会下雨。如果一个城市在接下来的m天内永远不会下雨，则称为干燥城市。多雷米有一个特殊能力，她可以选择k天，在这几天内不会下雨。多雷米想要计算使用特殊能力后，干燥城市的最大数量。 输入数据格式： 输入包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含三个整数n、m和k（1≤n≤2×10^5，2≤m≤2×10^5，2≤k≤min(10, m)）——城市的数量、天数和Doremy可以阻止的雨天数量。 然后是m行，第i行包含两个整数l_i、r_i（1≤l_i≤r_i≤n）——第i天的降雨范围。 保证所有测试用例的n和m的总和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——干燥城市的最大数量。 示例： 输入： 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 2 6 0 1000 17 注意： 在第一个测试用例中，如果多雷米阻止1,2天的雨，那么城市2将变干；如果阻止2,3天的雨，那么没有城市会变干；如果阻止1,3天的雨，那么没有城市会变干。因此，最多有1个干燥城市。 在第二个测试用例中，如果多雷米阻止1,2天的雨，那么城市1,2将变干；如果阻止2,3天的雨，那么城市4,5将变干；如果阻止1,3天的雨，那么城市1,5将变干。因此，最多有2个干燥城市。 在第三个测试用例中，最优的做法是阻止1,2,4,5天的雨。 在第四个测试用例中，总有一天会下雨，淋湿所有城市，无法阻止。