C2. План осушения от Дореми (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Единственное различие между двумя версиями этой задачи — ограничение на $$$k$$$, ограничение по времени и ограничение по памяти. Делать взломы можно только в том случае, если решены обе версии задачи.

Дореми живет в дождливой стране, состоящей из $$$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)$$$) — количество городов, количество дней и количество дней дождя, которые может предотвратить Дореми.

Далее следуют $$$m$$$ строк. В $$$i$$$-й строке содержатся два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — отрезок городов, в которых будет дождь в день $$$i$$$.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышает $$$2\cdot 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$$$.

В четвертом наборе входных данных всегда есть день дождя, который промочит все города, вне зависимости от использования силы.