22991번 - 수요응답형 버스

현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호출하면 실시간으로 가장 빠른 경로가 생성되고 배차가 이뤄지는 수요응답형 버스로, 노선 체계가 갖춰지기 시작하는 도시개발 중간단계에서 주민들의 이용 편의를 향상시킬 수 있는 신개념 모빌리티 솔루션이다. 고정된 노선 없이 실시간 호출에 의해 배차되고 운행되므로 시민의 차량 대기 시간과 이동 시간이 단축돼 대중교통 편의성이 크게 향상된다.

당신은 출퇴근 시간처럼 호출이 몰렸을 때, 동시에 매칭해주는 시스템을 개발하고 있다. 배차 요청은 $N$ 개가 들어왔고, 각 배차 요청은 탑승 인원과 최대 대기 가능 시간으로 이루어져 있다. 버스는 $M$ 대가 있고, 각 버스에는 정원과 도착 예정 시간이 있다. 또한 버스는 도착하면 $1$분 이상 기다리지 않고 떠난다. 

어떤 배차 요청에 버스를 배정할 수 있으려면, 버스의 정원이 탑승 인원보다 크거나 같아야 하며, 도착 예정 시간이 최대 대기 가능 시간보다 작거나 같아야 한다. 예를 들어 탑승 인원이 $4$명이고 최대 대기 가능 시간이 $7$분이면, 정원이 $4$명 이상이고, 도착 예정 시간이 $7$분 이내인 버스를 배차할 수 있다.

배차 요청과 버스를 대응시킬 때, 서로 1:1 대응시켜야 한다는 제약사항이 있다. 즉, 하나의 배차 요청을 두 대 이상의 버스에 배정할 수 없으며, 반대로 하나의 버스가 두 개 이상의 배차 요청에 배정되는 것은 정책상 허락하지 않기로 하였다. 또한, 같은 시간에 여러 개의 요청을 동시에 처리할 수 있다. 

당신은 최대한 많은 배차 요청에 버스를 대응시켜주는 프로그램을 구현해야 한다.

다음과 같이 입력이 주어진다.

• $N$은 배차 요청의 수이고, $M$은 버스의 수이다. ($1 \le N, M \le 200\ 000$)
• $a_i$와 $b_i$는 배차 요청의 정보를 나타낸다. $i$ 번째 배차 요청의 탑승 인원이 $a_i$ 명이고, 최대 대기 가능 시간이 $b_i$ 분임을 나타낸다. ($1 \le a_i, b_i \le 10^9$)
• $c_j$와 $d_j$는 버스의 정보를 나타낸다. $j$ 번째 버스의 정원이 $c_j$ 명이고, 도착 예정 시간이 $d_j$ 분임을 나타낸다. ($1 \le c_j, d_j \le 10^9$)
• 입력으로 주어지는 모든 수는 정수다.

첫 번째 줄에 버스를 배정할 수 있는 배차 요청 수의 최댓값을 출력하여라.