A105172.糖果店的购物挑战

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

SherrySherry 放学后去了附近的糖果店,糖果店里有 NN 个不同的糖果盒子,每个盒子的价格和其中的糖果数量各不相同。

糖果店的商品编号为 11NN,每个盒子 ii 的价格和其中糖果的数量分别用整数 AiA_i 表示。SherrySherry 打算从这些盒子中购买 MM 个,并将这些盒子里的糖果分发给班级的 MM 个人。每个班级成员都有不同的糖果需求,即第 ii 个人需要至少 BiB_i 块糖果。

SherrySherry 希望购买 MM 个盒子来满足这些需求,且要求购买的盒子的总费用尽量最小。如果无法满足条件,则需要输出 -1

输入格式

第一行输入两个整数 NNMM,表示店内售出的盒子数量以及 SherrySherry 需要买的盒子数量。
第二行输入 NN 个正整数,第 ii 个整数 AiA_i 表示第 ii 个盒子装了 AiA_i 块糖果,并且需要 AiA_i 元。
第三行输入 MM 个正整数,第 ii 个正整数 BiB_i 表示第 ii 个人至少需要 BiB_i 块糖果。

输出格式

如果 SherrySherry 可以找到 MM 个符合条件的盒子,输出SherrySherry需要支付的最小总金额;否则输出 -1

输入输出样例

  • 输入#1

    4 2
    3 4 5 4
    1 4
    

    输出#1

    7
    
  • 输入#2

    3 3
    1 1 1
    1000000000 1000000000 1000000000
    

    输出#2

    -1
    

说明/提示

1MN2×1051 \leq M \leq N \leq 2 \times 10^5

1Ai,Bi1091 \leq A_i, B_i \leq 10^9

首页