COCI 2013/2014 - Contest 1- 배낭채우기3 (LOPOV) > 문제은행 : 정보올림피아드&알고리즘




2666 : 배낭채우기3 (LOPOV)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
24 회   
시도횟수
171 회   

문제

정올 보석상에 도둑이 침입했다. 도둑은 K개의 배낭에 훔친 보석을 담으려고 한다. 이때, 각 배낭에 2개 이상의 보석을 넣거나 무게가 Wt 보다 큰 보석을 넣으면 배낭이 망가진다.

 


각 보석의 값어치와 무게가 주어질 때, 도둑은 보석의 총 값어치가 최대가 되도록 보석을 배낭에 담으려고 한다. 이때 배낭에 담을 수 있는 최대 값어치를 구하시오.


입력형식

첫 번째 줄에는 보석의 수 N과 배낭의 수 K가 주어진다. (1 ≤ N, K ≤ 300,000)
두 번째 줄부터 N개의 줄에는 각 보석의 무게와 값어치가 주어진다. 무게와 값어치는 1,000,000 이하의 자연수이다.
그 다음 줄부터 K개의 줄에는 Wt 가 주어진다. (1 ≤ Wt ≤ 100,000,000)


출력형식

도둑이 담을 수 있는 보석의 총 값어치의 최댓값을 출력한다.


입력 예

2 1
5 10
100 100
11

출력 예

10

입력 예

3 2
1 65
5 23
2 99
10
2

출력 예

164


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP