2126 : 선탠
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 2 회
- 시도횟수
- 5 회
문제
선탠 도중 화상을 입는 것을 막기 위해서, C (1 이상 2,500 이하)마리의 소들은 자외선 차단 로션을 가죽에 바르려고 한다. 소 i는 최소 SPF와 최대 SPF 값이 있다(1 ≤ 최소 SPF_i ≤ 최대 SPF_i ≤ 1,000). 만약 최소 SPF보다 작은 SPF의 로션을 바르면 가죽이 화상을 입게 되고, 최대 SPF보다 큰 SPF의 로션을 바르면 선탠이 전혀 되지 않는다.
소들은 피크닉 바구니에 L(1 이상 2,500 이하)병의 자외선 차단 로션을 가져왔다. i번째 로션은 SPF_i(1 이상 1,000 이하)의 SPF 값을 가지고 있고, 최대 cover_i마리의 소들이 이 로션을 사용할 수 있다. 각 소는 최대 하나의 로션만 사용할 수 있다.
각자의 SPF 범위를 만족하도록 로션을 바를 수 있는 소들의 수는 최대 몇 마리인지 계산하자.
입력형식
첫 번째 줄에 공백으로 구분된 두 개의 정수 C와 L이 입력된다.
이후 C개의 줄에 걸쳐 i번째 소를 나타내는 두 개의 정수 최소 SPF_i와 최대 SPF_i가 공백으로 구분되어 주어진다.
이후 L개의 줄에 걸쳐 i번째 로션을 나타내는 두 개의 정수 SPF_i와 cover_i가 주어진다.
출력형식
로션을 사용할 수 있는 소의 최대 마리수를 출력한다.
입력 예3 2 3 10 2 5 1 5 6 2 4 1 |
출력 예2 |