Background

There are some items and a thief.

Problem Description

There are $N$ items. Each item has a weight $M_i$ and a value $V_i$.

Mirko has $K$ bags. The maximum weight each bag can hold is $C_i$.

Each bag can contain only one item. What is the maximum total value of items that can be taken?

Input Format

The first line contains two positive integers $N$ and $K$.

Each of the next $N$ lines contains two positive integers $M_i$ and $V_i$.

Each of the next $K$ lines contains one positive integer $C_i$.

Output Format

Output one line: the maximum total value of the items that can be taken.

2 1
5 10
100 100
11 

10

3 2
1 65
5 23
2 99
10
2

164

Hint

Constraints

• $1 \le N, K \le 3 \times 10^5$.
• $1 \le M_i, V_i \le 10^6$.
• $1 \le C_i \le 10^8$.

Explanation for Sample 2

Mirko puts the first item into the second bag, and the third item into the first bag.

Notes

This problem is translated from COCI2013-2014 CONTEST #1 T4 LOPOV.

Translated by ChatGPT 5