맛있는 걸 좋아하는 소들 > 문제은행

본문 바로가기


알고리즘 자료구조2

2287 : 맛있는 걸 좋아하는 소들

제한시간: 3000 ms    메모리제한: 128 MB
해결횟수: 48 회    시도횟수: 242 회   



농부 건규의 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을 출력한다.

[Copy]
4 7
1 1
2 3
1 4
4 2
3 2
2 1
4 3
5 2
5 4
2 6
4 4
[Copy]
12



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.