페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2666

배낭채우기3 (LOPOV) 1초 32MB

문제

정올 보석상에 도둑이 침입했다.

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

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


입력

첫 번째 줄에는 보석의 수 N과 배낭의 수 K가 주어진다. (1 ≤ N, K ≤ 300,000)

두 번째 줄부터 N개의 줄에는 각 보석의 무게와 값어치가 주어진다. 무게와 값어치는 1,000,000 이하의 자연수이다.

그 다음 줄부터 K개의 줄에는 W_t 가 주어진다. (1 ≤ W_t ≤ 100,000,000)


출력

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


예제1

입력
21

510

100100

11
출력
10

예제2

입력
32

165

523

299

10

2
출력
164

출처

COCI 2013/2014 - Contest 1

역링크