6571：Packing

Avin’s warehouse has a packing line with m outlets. There are n goods in total, which aren’t on the packing line. And the i-th good will be sent to the xi outlet at time ti . In each second, Avin can send at most one good from one outlet to the packing line. For outlet i, there is an associated buffer with size ai, and goods can be placed in the buffer. However, at the end of each second, if the number of goods b at the outlet is greater than ai , Avin has to pay the utilization fee b - ai . Since Avin wants to save money, he asks you to find a plan to send all the goods to the packing line with minimum utilization fee. In order to finish today’s work, Avin must send all goods to the packing line. Goods arrived at time ti can be sent to the packing line immediately at time ti.

The first line contains two integers n and m (1 ≤ n, m ≤ 1, 000, 000) . In the following n lines, each of which contains two numbers ti (1 ≤ ti ≤ 1, 000, 000) and xi (1 ≤ xi ≤ m). In the next following line, there are m integers containing ai (1 ≤ ai ≤ 1, 000, 000).

Print the minimum utilization fee.