Doremy 的干燥计划（困难版）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

一个国家有 $n$ 个城市，编号为 $1$ 到 $n$。天气预报给出了未来 $m$ 天的降雨：第 $i$ 天，区间 $[l_i,r_i]$ 内的所有城市都会下雨。

如果一个城市在未来 $m$ 天中从未下雨，则称它为干燥城市。Doremy 可以选择恰好 $k$ 天，使这些天的降雨全部取消。请计算取消后最多能有多少个干燥城市。

输入格式

第一行一个整数 $t$，表示测试用例数量。

每个测试用例第一行三个整数 $n,m,k$，分别表示城市数、天数和可以取消的降雨天数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示第 $i$ 天的降雨区间。

输出格式

对每个测试用例输出一行一个整数，表示最多的干燥城市数量。

样例输入 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

数据范围

$1\le t\le10^4$，$1\le n\le2\cdot10^5$，$2\le m\le2\cdot10^5$，$2\le k\le\min(10,m)$，$1\le l_i\le r_i\le n$。所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2\cdot10^5$。