USACO 2007 November Gold- 선탠 > 문제은행 : 정보올림피아드&알고리즘




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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP