보석 도둑
면접 대비시간 제한1초메모리 제한256 MB
무게와 가치가 있는 보석 N개와 무게 제한이 있는 가방 K개가 주어질 때, 가방마다 보석을 하나씩 담아 훔친 보석의 총 가치를 최대화합니다.
문제
한 도둑이 보석점에서 보석을 훔치려고 한다.
보석점에는 보석이 N개 있다. i번째 보석의 무게는 M_i, 가격은 V_i이다. 도둑은 가방을 K개 가지고 있으며, j번째 가방에는 무게가 C_j 이하인 보석을 담을 수 있다.
각 가방에는 보석을 최대 한 개만 넣을 수 있고, 각 보석도 최대 한 번만 훔칠 수 있다. 훔칠 수 있는 보석 가격의 합이 최대가 되도록 할 때, 그 최댓값을 구하라.
입력
첫째 줄에 보석의 개수 N과 가방의 개수 K가 주어진다. (1 <= N, K <= 300,000)
다음 N개 줄에는 각 보석의 무게 M_i와 가격 V_i가 주어진다. (0 <= M_i, V_i <= 1,000,000)
다음 K개 줄에는 각 가방에 담을 수 있는 최대 무게 C_j가 주어진다. (1 <= C_j <= 100,000,000)
입력으로 주어지는 모든 값은 정수이다.
출력
훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
힌트
두 번째 공개 테스트에서는 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 총 가격이 164가 된다.