1028 : Xiaoming Orders Takeaway

Description

Xiaoming likes to stay at home and takeaways are his favorate. He has accumulated n full discount coupons and wants to make an ordering plan for the next few days.

He will order a total of m takeaways on different days 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 100 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 takeaways. Each line contains Oi means the prise of the i-th order.

1 <= n <= 100, 1 <= m <= 100, 1 <= Di <= Ci <= 100, 1 <= Oi <= 100.

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