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

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

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

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

맛있는 걸 좋아하는 소들 timer 3s memory 128MB

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