小红准备买件物品，第件物品的价格是。另外，小红有种优惠券，第个优惠券是：买一件价格不小于的商品时，可以减去的价格。每件商品最多只能用一次优惠券。每种优惠券可以用多次。 小红想知道，自己买全部商品最少需要花多少钱？

输入描述:

第一行输入两个正整数，代表商品数量和优惠券的种类数。第二行输入个正整数，代表每件商品的价格。接下来的行，每行输入两个正整数，代表第种优惠券的信息。

输出描述:

一个正整数，代表最终需要花的最少钱数。