310798: CF1889C2. Doremy's Drying Plan (Hard Version)

C2. 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 \le t \le 10^4 $）—— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $ n $、$ m $ 和 $ k $（$ 1 \le n \le 2 \times 10^5 $，$ 2 \le m \le 2 \times 10^5 $，$ 2 \le k \le \min(10, m) $）—— 城市数量、天数以及多雷米可以防止下雨的天数。

然后是 $ m $ 行，第 $ i $ 行包含两个整数 $ l_i $、$ r_i $（$ 1 \le l_i \le r_i \le n $）—— 第 $ i $ 天的降雨覆盖范围。

保证所有测试用例的 $ n $ 和 $ m $ 之和不超过 $ 2 \times 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
```

**注意：**

- 在第一个测试用例中，如果多雷米阻止前两天的雨，那么城市 $ 2 $ 将是干城市。
- 在第二个测试用例中，如果多雷米阻止第一和第二天的雨，那么城市 $ 1 $ 和 $ 2 $ 将是干城市。
- 在第三个测试用例中，最优方案是阻止第一、二、四、五天的雨。
- 在第四个测试用例中，总有一天会下雨并淋湿所有城市，且这一天无法被阻止。**题目大意：** 多雷米（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 \times 10^5 $，$ 2 \le m \le 2 \times 10^5 $，$ 2 \le k \le \min(10, m) $）—— 城市数量、天数以及多雷米可以防止下雨的天数。 然后是 $ m $ 行，第 $ i $ 行包含两个整数 $ l_i $、$ r_i $（$ 1 \le l_i \le r_i \le n $）—— 第 $ i $ 天的降雨覆盖范围。 保证所有测试用例的 $ n $ 和 $ m $ 之和不超过 $ 2 \times 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 ``` **注意：** - 在第一个测试用例中，如果多雷米阻止前两天的雨，那么城市 $ 2 $ 将是干城市。 - 在第二个测试用例中，如果多雷米阻止第一和第二天的雨，那么城市 $ 1 $ 和 $ 2 $ 将是干城市。 - 在第三个测试用例中，最优方案是阻止第一、二、四、五天的雨。 - 在第四个测试用例中，总有一天会下雨并淋湿所有城市，且这一天无法被阻止。