题目内容

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

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

题解

题面描述

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

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