10115 보석 도둑 Gold II

문제

N개의 보석과 K개의 가방이 있다. 각 보석은 무게와 가치가 있고, 각 가방에는 최대 무게 제한이 있다. 가방 하나에 보석 하나만 넣을 수 있을 때, 훔칠 수 있는 보석 가치의 최댓값을 구하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 300,000)과 K (1 ≤ K ≤ 300,000)가 주어진다. 다음 N줄에 보석 정보 (무게, 가치), 다음 K줄에 가방 용량이 주어진다.

출력

최대 가치를 출력한다.

2 1
5 10
100 100
11

10