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

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

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