32511번 - 작업 처리

$N$ 개의 작업이 있다. 각 작업은 두 정수 $s, t$ 로 표현되며 ($s < t$), 이는 해당 작업이 $s$ 에 시작해서 $t$ 에 종료됨을 뜻한다. 두 작업의 작업 기간이 겹치면 두 작업을 모두 수행할 수는 없다. (단, 어느 한 작업의 종료 시각과 다른 한 작업의 시작 시각이 같다면 작업 기간이 겹치지 않는 것으로 본다.)

어떠한 공장에서는 최대한 많은 작업을 처리하려고 하는데, 위에서 설명한 대로 한 시점에 최대 하나의 작업밖에 처리하지 못 하기 때문에 처리할 수 있는 작업에 한계가 있다. 공장을 확장하는 대신, 더 다양한 작업들을 추가해서 이 문제를 해결하려고 한다.

$Q$ 개의 질의가 주어진다. $i$ 번 질의에는 $R_i$ 개의 작업이 추가로 주어진다. 각 질의에 대해, $N + R_i$ 개의 작업 중 처리할 수 있는 최대 개수 작업의 개수를 출력하여라.

예를 들어, $N=4$, $Q=2$이고 기본 작업을 시작 시각과 종료 시각의 쌍으로 표현했을 때의 집합이 $\{(1, 5), (5, 10), (14, 16), (2, 9)\}$, 질의 2개는 $\{(3, 7), (11, 14)\}, \{(4, 8), (13, 15)\}$ 라고 하자. 첫번째 질의에 대해서는 $\{(1, 5), (5, 10), (11, 14), (14, 16)\}$ 의 총 4개의 작업을 수행하는 것이 최적이며, 두번째 질의에 대해서는 $\{(1, 5), (5, 10), (14, 16)\}$의 총 3개의 작업을 수행하는 것이 최적이다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스의 첫 줄에는 작업의 수 $N$이 주어진다. ($1 \le N \le 120\,000$)

이후 $N$ 개의 줄에 작업의 시작 시간과 종료 시간 $s, t$ 가 주어진다. ($0 \le s < t \le 10^9$)

다음 줄에 질의의 수 $Q$ 가 주어진다. ($1 \le Q \le 60\,000$)

이후 각 질의가 다음과 같이 주어진다. 각 질의의 첫 줄에는 새 작업의 개수 $R_i$ 가 주어진다. ($1 \le R_i \le 120\,000, 1 \le \sum R_i \le 120\,000$)

이후 $R_i$ 개의 줄에 작업의 시작 시간과 종료 시간 $s, t$ 가 주어진다. ($0 \le s < t \le 10^9$)

모든 테스트 케이스들에 대한 $N$ 의 합은 $1\,300\,000$ 이하이다.

모든 테스트 케이스들에 대한 $\sum R_i$ 의 합은 $1\,100\,000$ 이하이다.

각 테스트 케이스마다 첫 줄에는 Case #$C$ 를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

이후 $Q$ 개 줄에 걸쳐 각 질의의 답을 출력하라.