문제
선탠 도중 화상을 입는 것을 막기 위해서, 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가 주어진다.
출력
로션을 사용할 수 있는 소의 최대 마리수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | |
| #2 | 15점 | |
| #3 | 80점 | 추가 제한사항 없음 |
예제
3 2
3 10
2 5
1 5
6 2
4 1
2
출처
USACO 2007 November Gold
로그인해야 코드를 작성할 수 있어요.