Minimum Purchase Cost with Discount Coupons

You are given n items and m discount coupons. The i^th item has an original price \(a_i\) and a discounted price \(b_i\) (with \(b_i \le a_i\)). You also have m coupons. The j^th coupon is of the form "if the original price is at least \(w_j\), then subtract \(v_j\)" (with \(v_j \le w_j\)).

For each item \(i\), you can choose one of the following three purchase methods:

1. Buy it at its original price \(a_i\).
2. Buy it at its discounted price \(b_i\).
3. Use one unused coupon \(j\) provided that \(a_i \ge w_j\) and pay \(a_i - v_j\) (note that each coupon can be used for at most one item).

Your task is to determine the minimum total amount of money needed to purchase all items.

Formally, if you choose to use a coupon on item \(i\), its cost becomes \(a_i - v_j\). If no coupon is used, the cost is \(b_i\) (since \(b_i \le a_i\)). You need to assign coupons (if beneficial) so that the overall cost is minimized.

Note: A coupon \(j\) can only be used if \(a_i \ge w_j\) and it is beneficial to use the coupon only if \(a_i - v_j < b_i\), i.e. \(v_j > a_i - b_i\). The answer is the sum over all items of the chosen cost.

The problem may be solved optimally using a greedy strategy with a priority queue.

inputFormat

The input is given as follows:

 n m
 a1 a2 ... an
 b1 b2 ... bn
 w1 v1
 w2 v2
 ...
 wm vm

• \(n\) is the number of items.
• \(m\) is the number of coupons.
• The second line contains \(n\) integers \(a_i\), the original prices of the items.
• The third line contains \(n\) integers \(b_i\), the discounted prices of the items.
• Then follow \(m\) lines, each containing two integers \(w_j\) and \(v_j\), which describe a coupon.

outputFormat

Output a single integer representing the minimum total cost to purchase all items.

sample

2 1
100 101
50 100
100 70

81