A105172.糖果店的购物挑战
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Sherry 放学后去了附近的糖果店,糖果店里有 N 个不同的糖果盒子,每个盒子的价格和其中的糖果数量各不相同。
糖果店的商品编号为 1 至 N,每个盒子 i 的价格和其中糖果的数量分别用整数 Ai 表示。Sherry 打算从这些盒子中购买 M 个,并将这些盒子里的糖果分发给班级的 M 个人。每个班级成员都有不同的糖果需求,即第 i 个人需要至少 Bi 块糖果。
Sherry 希望购买 M 个盒子来满足这些需求,且要求购买的盒子的总费用尽量最小。如果无法满足条件,则需要输出 -1。
输入格式
第一行输入两个整数 N 和 M,表示店内售出的盒子数量以及 Sherry 需要买的盒子数量。
第二行输入 N 个正整数,第 i 个整数 Ai 表示第 i 个盒子装了 Ai 块糖果,并且需要 Ai 元。
第三行输入 M 个正整数,第 i 个正整数 Bi 表示第 i 个人至少需要 Bi 块糖果。
输出格式
如果 Sherry 可以找到 M 个符合条件的盒子,输出Sherry需要支付的最小总金额;否则输出 -1。
输入输出样例
输入#1
4 2 3 4 5 4 1 4
输出#1
7
输入#2
3 3 1 1 1 1000000000 1000000000 1000000000
输出#2
-1
说明/提示
1≤M≤N≤2×105。
1≤Ai,Bi≤109。