题解

题面描述

多多购物车内有$n$件商品，对于第$i$件商品价格是$p_i$元。另外多多有$m$张优惠券，每种优惠券只能用一次。第$j$张优惠券需要满$a_j$元才能使用，使用后可减免$b_j$元（且$b_j\le a_j$）。每张优惠券最多分配给一个商品，且每个商品最多使用一张优惠券。

目标是：分配优惠券到部分或全部商品上，使得总减免金额最大，并输出最大总减免值。

题目内容

多多购物车内有$n$件商品，对于第$i$件商品价格是$p_i$元。另外多多有$m$张优惠券，每种优惠券只能用一次。第$j$张优惠券需要满$a_j$元才能使用，使用后可减免$b_j$元$(b_j<=a_j)$。每张优惠券最多分配给一个商品，且每个商品最多使用一张优惠券。

多多想购买购物车所有的商品，请设计一种优惠券分配方案，使得总减免金额最大，并输出最大总减免。

输入描述

第一行包含两个整数n和m，分别表示商品数量和优惠券数量。$(1≤n,m≤100000)$

第二行包含$n$个整数$p_1$,$p_2$,...$p_n$表示各商品的价格$(1≤p_j≤100000)$

接下来m行，每行两个整数$a_j,b_j$表示第$j$张优惠券的门槛和减免金额$(1≤b_j≤a_j≤100000)$

输出描述

一个整数,表示最大总减免金额

样例1

输入

3 2
15 20 25
20 5
25 8

输出

13

说明

满$20$减$5$的优惠券分配给价格$15$的商品，满$25$减$8$的优惠券分配给价格25的商品，一共减免$13$元。

样例2

输入

2 2
10 20
15 3
20 4

输出

4