#3044. I. Package Delivery
-
ID: 3044
传统题
6000ms
512MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
2000170131
I. Package Delivery
Description
Little Q likes online shopping very much. In the next 109 days, there will be n packages delivered to thepost office in total. Let’s label the next 109 days as day 1, day 2, . . . , day 109 respectively. For the i-th
package, it will arrive at the post office at day li, and the deadline to take it back home is day ri, which
means Little Q can take it back home at day x if and only if li ≤ x ≤ ri.
Every time Little Q comes to the post office, he can take at most k packages together back home at the
same time. Note that Little Q can go to the post office multiple times during a single day. Please help
Little Q determine how to take these n packages back home such that the number of times he will go to
the post office is minimized.
Input Format
The first line contains a single integer T (1 ≤ T ≤ 3 000), the number of test cases. For each test case:The first line contains two integers n and k (1 ≤ k ≤ n ≤ 100 000), denoting the number of packages and
the number of packages Little Q can carry at the same time.
Each of the following n lines contains two integers li and ri (1 ≤ li ≤ ri ≤ 109), describing a package.
It is guaranteed that the sum of all n is at most 1 000 000.
Output Format
For each test case, output a single line containing an integer, denoting the minimum possible number oftimes that Little Q will go to the post office
1
4 2
1 3
2 4
6 7
4 72