Page not loading? Try clicking here.
Placeholder

#2666

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

Problems

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

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

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


Input

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

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

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


Output

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


Example #1

2 1

5 10

100 100

11
10

Example #2

3 2

1 65

5 23

2 99

10

2
164


Source

COCI 2013/2014 - Contest 1

You must sign in to write code.