题目详情题解（0）讨论（0）提交记录（0）

CF1889C2.Doremy's Drying Plan (Hard Version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

The only differences between the two versions of this problem are the constraint on kk , 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 nn cities numbered from 11 to nn .

The weather broadcast predicted the distribution of rain in the next mm days. In the ii -th day, it will rain in the cities in the interval [li,ri][l_i, r_i] . A city is called dry if it will never rain in that city in the next mm days.

It turns out that Doremy has a special power. She can choose kk 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 tt ( 1≤t≤1041\le t\le 10^4 ) — the number of test cases. The description of the test cases follows.

The first line contains three integers nn , mm and kk ( 1≤n≤2⋅1051\le n\le 2\cdot 10^5 , 2≤m≤2⋅1052 \le m \le 2\cdot 10^5 , 2≤k≤min⁡(10,m)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, mm lines follow. The ii -th line contains two integers lil_i , rir_i ( 1≤li≤ri≤n1\le l_i\le r_i\le n ) — the rain coverage on day ii .

It is guaranteed that the sum of nn and the sum of mm over all test cases do not exceed 2⋅1052\cdot 10^5 .

输出格式

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

输入输出样例

  • 输入#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

说明/提示

In the first test case, if Doremy prevents

  • rain 1,21,2 , then city 22 will be dry;
  • rain 2,32,3 , then no city will be dry;
  • rain 1,31,3 , then no city will be dry;

So there is at most 11 dry city.

In the second test case, if Doremy prevents

  • rain 1,21,2 , then city 1,21,2 will be dry;
  • rain 2,32,3 , then city 4,54,5 will be dry;
  • rain 1,31,3 , then city 1,51,5 will be dry.

So there are at most 22 dry cities.

In the third test case, it is optimal to prevent rain 1,2,4,51,2,4,5 .

In the forth test case, there is always a day of rain that wets all the cities and cannot be prevented.

首页