맛있는 걸 좋아하는 소들

농부 건규의 N (1≤N≤100,000) 마리의 소들은 혀가 고급이어서 반드시 푸른 풀 식료품점에서 풀을 사먹어야 한다.

소들의 입맛이 까다로워서 i번째 소는 A_i 보다 가격이 같거나 비싸고, B_i 보다 맛이 같거나 좋은 풀을 사먹길 원한다.

푸른 풀 식료품점에는 M (1≤M≤100,000)개 종류의 풀이 있다. i번째 풀의 가격은 C_i 이고 맛의 강도는 D_i 이다. 각 풀은 한 소에게만 팔 수 있다.

최소의 가격으로 모든 소들이 만족 하는 풀을 사도록 해보자 (1<=A_i,B_i,C_i,D_i≤1,000,000,000).

입력

첫 번째 줄에는 N과 M가 공백으로 구분되어 주어진다.

다음 줄 부터 N개의 줄에는 A_i, B_i가 주어지며,

처음에는 A_1, B_1가, 다음에는 A_2, B_2가 들어오는 형식으로 입력된다.

그 다음 줄부터는 M개의 줄에 C_i와 D_i가 주어지며,

처음에는 C_1, D_1가, 다음에는 C_2, D_2가 들어오는 형식으로 입력된다.

출력

모든 소들이 만족할 수 있는 풀을 사도록 하는 최소의 가격을 출력한다.

만약 모든 소들을 만족 시킬 수 없다면 -1을 출력한다.

예제1

출처

USACO December 2007 Gold

맛있는 걸 좋아하는 소들 3초 128MB