秋招模拟赛第40场|2023.09.02-京东
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2023-9-7 19:00
- End at
- 2023-9-7 20:30
- Duration
- 1.5 hour(s)
- Host
- Partic.
- 22
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
塔子哥最近在公司表现不错,老板奖励了他一堆优惠券。
正巧塔子哥需要购买一些生活用品,于是他来到了商场。
他购买了 n 件商品,第 i 件商品的价格为 pi 。
他有 m 种优惠券,每种优惠券可以使用任意多次,但是每件商品只能使用一张优惠券
第 i 种优惠券的使用条件为,当购买的一件商品的价格不低于 ai 时,可以减去 bi 的钱。
现在塔子哥问你,购买这 n 种商品,他最少需要花多少钱。
第一行,两个整数 n,m(1≤n,m≤2×105)
第二行,n 个整数 pi(1≤pi≤109) ,第 i 个数为第 i 件商品的价格。
接下来 m 行,每行 2 个整数,分别为 ai 和 bi(1≤bi<ai≤109) ,含义见题面 。
一个整数,表示塔子哥购买这 n 种商品最少需要花的钱。
输入
3 3
4 6 8
3 2
4 3
9 5
输出
9
说明
三件商品都使用第二种优惠券
总价格为 (4+6+8)-3-3-3=9
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.