1029 : Xiaoming Orders Rockets

Description

In the year 2077, Xiao Ming has grown up and become a scientist. He need to order some light rockets for experiments during the next few days.

Times have changed, the world has not changed – He has a series of discount coupons.

He will order a total of m rockets in different times and wants to know the least money will be spent by using coupons wisely.

One order at a time, and at most one coupon can be used for each order.

Input

There are no more than 10 test cases.

On the first line of each test case, two integer numbers n and m are given. The number of coupons and orders.

Then n lines follow. Each line contains Ci and Di means you need to spend at least Ci to get Di price reduction when using the i-th coupon.

After that, m lines describe the price of the m rockets. Each line contains Oi means the prise of the i-th order.

1 <= n <= 50000, 1 <= m <= 50000, 1 <= Di <= Ci <= 10^6, 1 <= Oi <= 10^6.

Output

For each test case output one line, the minimal cost for the orders.

Sample

2 2
5 3
7 2
4
8
4 5
1 1
1 1
6 3
8 7
7
3
1
6
10

9
15

Hint

Source

Author

CSGrandeur