CCC 캠프

Härryda에서 Chalmers Coding Club와 함께하는 새 캠프가 시작될 시간이다! 전통에 따라 모두가 3 AM까지 사우나에 있다가 이제 잠자리에 들었다. 캠프 참가자 전원은 크고 길쭉한 방(Storstugan)에서 함께 자고 있지만, 안타깝게도 긴 쪽 벽을 따라 곧 떠오를 아침 해를 정면으로 향한 창문도 있다. 참가자는 $N$명이며, $i$번째 참가자는 방의 문(짧은 쪽 벽에 있음)에서 $d_i$미터 떨어진 곳에서 잔다. 참가자들은 이층 침대에서 자기 때문에 여러 참가자가 문에서 같은 거리만큼 떨어진 곳에서 잘 수도 있다.

커튼이 빨간색으로 표시된 예제 1의 그림

Rasmus는 일찍 일어나 창문의 일부를 $M$개의 서로 다른 구간에서 가리는 커튼들이 있다는 것을 알아차렸다. 각 커튼은 문에서 $L$미터와 $R$미터 사이, 즉 양 끝을 포함한 범위에서 자는 모든 사람에게 햇빛이 닿지 않게 하여, 그들이 계속 잘 수 있게 한다. 여러 커튼이 창문의 같은 부분을 가릴 수도 있음에 유의한다. 안타깝게도 커튼의 어느 부분에도 가려지지 않은 사람들은 강렬한 아침 햇빛을 받아 즉시 잠에서 깬다.

일찍 일어나게 될 불쌍한 참가자들을 모두 돕기 위해 Rasmus는 커피를 만들 계획이다. 그는 각 참가자가 제대로 잠에서 깨려면 커피 한 잔이 필요하다고 생각하지만, Joshua와 Gustav는 다음 날 강의를 준비하느라 더 늦게까지 깨어 있었다는 것도 알고 있으므로, 두 사람에게는 커피가 두 잔씩 필요하다.

Rasmus는 커피를 몇 잔 만들어야 하는가?

채점

여러 테스트 그룹으로 해답을 테스트하며, 각 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 한 테스트 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$10$| $N, M \le 100$, $d_i, L_j, R_j \le 1000$

$2$ |$20$| $M \le 100$, $d_i, L_j, R_j \le 10^5$

$3$ |$20$| $d_i, L_j, R_j \le 10^5$

$4$ |$50$| 추가 제약 조건 없음.

첫째 줄에 참가자 수와 커튼 구간 수를 나타내는 두 정수 $N$과 $M$이 주어진다. ($1 \leq N \leq 2 \cdot 10^5$, $0 \leq M \leq 2 \cdot 10^5$).

이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 $i$번째 참가자의 이름과 그 참가자가 자는 곳의 문으로부터의 거리 $d_i$이 차례로 주어진다. ($0 \leq d_i \leq 10^9$). 각 이름은 3개 이상 10개 이하의 문자로 이루어진다. 이름은 대문자 하나(A-Z)로 시작하고, 그 뒤에 소문자들(a-z)이 이어진다. 각 참가자의 이름은 서로 다름이 보장된다.

다음 $M$개의 줄에는 각각 두 정수 $L$과 $R$이 주어지며, ($0 \le L_j \le R_j \le 10^9$), 이는 커튼 하나가 구간 $[L, R]$을 가린다는 뜻이다. 일부 커튼은 서로 겹칠 수도 있음에 유의한다.

새로 잠에서 깬 참가자들을 만족시키기 위해 Rasmus가 준비해야 하는 커피의 잔 수를 나타내는 정수 하나를 출력한다.

안타깝게도 Joshua, Jens, Gustav는 잠에서 깬다. Joshua와 Gustav는 각각 커피 두 잔이 필요하지만, Jens는 한 잔만 필요하다. 따라서 Rasmus는 총 5잔의 커피를 내려야 한다.