2287 : 맛있는 걸 좋아하는 소들
- 제한시간
- 3000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 25 회
- 시도횟수
- 63 회
문제
농부 건규의 N(1≤N≤100,000) 마리의 소들은 혀가 고급이어서
반드시 푸른 풀 식료품점(이하 GGG) 에서 풀을 사먹어야 한다.
역시나 까다로운 소들의 입맛이 문제다.
i번째 소는 Ai 보다 가격이 같거나 비싸고, Bi 보다 맛이 같거나 좋은 풀을 사먹길 원한다.
GGG 가게에는 M(1≤M≤100,000)개 종류의 풀이 있다.
i번째 풀의 가격은 Ci 이고 맛의 강도는 Di 이다. 각 풀은 한 소에게만 팔 수 있다.
최소의 가격으로 모든 소들이 만족 하는 풀을 사도록 해보자(1<=Ai,Bi,Ci,Di≤1,000,000,000).
입력형식
첫 번째 줄에는 N과 M가 공백으로 구분되어 주어진다.
다음 줄 부터 N개의 줄에는 Ai, Bi가 주어지며,
처음에는 A1, B1가, 다음에는 A2, B2가 들어오는 형식으로 입력된다.
그 다음 줄부터는 M개의 줄에 Ci와 Di가 주어지며,
처음에는 C1, D1가, 다음에는 C2, D2가 들어오는 형식으로 입력된다.
출력형식
모든 소들이 만족할 수 있는 풀을 사도록 하는 최소의 가격을 출력한다.
만약 모든 소들을 만족 시킬 수 없다면 -1을 출력한다.
입력 예4 7 1 1 2 3 1 4 4 2 3 2 2 1 4 3 5 2 5 4 2 6 4 4 |
출력 예12 |
