题目描述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

出题Author

CSGrandeur

来源Source