32146번 - 지문이 트리로 가득 찬 트리 문제

문제

트리 문제를 내야 했지만 트리를 쓰는 트리 문제를 이미 출제한 지호는 이번에는 트리를 쓰는 트리 문제 대신 지문이 트리로 가득 찬 트리 문제를 내기로 했다.

지문이 트리로 가득 찬 좋은 트리 문제를 내기 위해서는 다양한 트리 강의를 많이 들어 트리에 대한 트리스러운 지식을 많이 익혀야 한다. 다행히, 트리를 사랑하는 경기과학고에는 좋은 트리 강의가 $N$개나 있다. 그중 $i$번째 트리 강의는 시각 $a_i$부터 $b_i$까지 진행되며, 이 트리 강의를 들으면 트리 지식을 1ドル$만큼 얻을 수 있다. 이때, 어떤 두 트리 강의의 시간이 겹치지 않는다면 두 트리 강의를 모두 들어 트리에 대해 더 많이 공부하고 더 좋은 트리 문제를 만들 수 있다. 단, 두 트리 강의가 $a_i = b_j$ 또는 $b_i=a_j$를 만족하면 이 역시 두 트리 강의가 겹치는 것이다.

$N$개의 트리 강의 중 몇 개는 필수로 수강해야 하며, 나머지는 시간이 겹치지 않는 한에서 자유롭게 신청해서 들을 수 있다. 이때, 여러분은 지호가 얻을 수 있는 트리 지식의 최댓값을 구해야 한다.

그런데, 지호는 아직 필수로 수강해야 하는 트리 강의가 무엇인지 모른다. $M$개의 쿼리마다 필수 수강해야 하는 트리 강의 몇 개가 주어지면, 각 쿼리에 대해 지호가 얻을 수 있는 트리 지식의 최댓값을 출력하여라.

입력

첫 번째 줄에 $N, M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄 중 $i$번째 줄에 $i$번째 트리 강의의 시작 및 종료 시각을 나타내는 두 정수 $a_i,ドル $b_i$가 공백으로 구분되어 주어진다.

그 다음 줄부터 $M$개의 줄에 걸쳐 한 줄에 하나씩 쿼리가 주어지며, 각 쿼리에는 필수로 수강해야 하는 트리 강의의 개수를 나타내는 정수 $s$와 $s$개의 트리 강의의 번호 $p_1, p_2, \cdots, p_s$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄부터 $M$개의 줄 중 $i$번째 줄에 $i$번째 쿼리에서 지호가 얻을 수 있는 트리 지식의 최댓값을 출력하여라.

제한

• 1ドル \leq N, M \leq 300,000円$
• 1ドル \leq a_i < b_i \leq 10^9$ (1ドル \leq i \leq N$)
• (모든 쿼리에서 $s$의 합) $\leq 300,000円$
• 각 쿼리에서 $b_{p_i} < a_{p_{i+1}}$ (1ドル \leq i < s$)
• 각 쿼리에서 $s>0$

힌트

서로 다른 두 트리 강의가 정확히 같은 시각에 시작하고 끝날 수도 있다.

이 문제의 지문에는 단어 '트리'가 총 36번 (제목까지 38번) 나온다. 지호는 지문이 트리로 가득 찬 좋은 트리 문제를 만드는 데 성공한 것 같다.