선크림

면접 대비

시간 제한1초메모리 제한128 MB

요약

소마다 허용하는 SPF 구간이 있고 병마다 SPF 값과 사용 가능한 소 수가 정해져 있을 때, 최대로 보호할 수 있는 소의 수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 구간, 투 포인터
정답자: 아직 제출이 없습니다

문제

해변에서 태닝을 하는 소들이 보기 흉한 화상을 입지 않으려면 각자 피부에 선크림을 발라야 한다. 소는 모두 $C$ 마리이며 ( $1 \le C \le 2500$ ), 소 $i$ 는 자신에게 맞는 SPF 지수의 최솟값 $\text{minSPF}_i$ 와 최댓값 $\text{maxSPF}_i$ 를 가진다 ( $1 \le \text{minSPF}_i \le 1000$ , $\text{minSPF}_i \le \text{maxSPF}_i \le 1000$ ). SPF 지수가 너무 낮으면 소는 화상을 입고, 너무 높으면 전혀 태닝이 되지 않는다.

소들은 선크림 로션 $L$ 병을 가지고 있다 ( $1 \le L \le 2500$ ). 병 $i$ 의 SPF 지수는 $\text{SPF}_i$ 이며 ( $1 \le \text{SPF}_i \le 1000$ ), 이 병으로는 최대 $\text{cover}_i$ 마리의 소에게 로션을 발라 줄 수 있다. 각 소는 오직 한 병의 로션만 사용할 수 있다.

소 $i$ 가 병 $j$ 의 로션으로 보호받으려면 $\text{minSPF}_i \le \text{SPF}_j \le \text{maxSPF}_i$ 를 만족해야 한다. 주어진 로션으로 태닝하면서 보호받을 수 있는 소의 최대 마릿수는 얼마인가?

입력

첫째 줄: 공백으로 구분된 두 정수 $C$ 와 $L$ .
다음 $C$ 개의 줄: $i$ 번째 줄에는 소 $i$ 의 조건을 나타내는 두 정수 $\text{minSPF}_i$ 와 $\text{maxSPF}_i$ 가 주어진다.
그다음 $L$ 개의 줄: 각 줄에는 로션 병 하나의 정보인 두 정수 $\text{SPF}_i$ 와 $\text{cover}_i$ 가 공백으로 구분되어 주어진다.

출력

태닝하면서 보호받을 수 있는 소의 최대 마릿수를 정수 하나로 한 줄에 출력한다.

예제4

예제 1
입력
```
3 2
3 10
2 5
1 5
6 2
4 1
```
예상 출력
```
2
```
예제 2
입력
```
1 1
5 10
3 1
```
예상 출력
```
0
```
예제 3
입력
```
1 1
1 4
5 1
```
예상 출력
```
0
```
예제 4
입력
```
3 1
1 10
1 10
1 10
5 3
```
예상 출력
```
3
```