

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
AtCoder Land のお土産屋に N 個の箱が売られています。
箱には 1, 2, \ldots, N の番号が付いており、箱 i の価格は A_i 円であり、A_i 個のお菓子が入っています。
高橋君は N 個の箱のうち M 個の箱を選んで買って帰り、1, 2, \ldots, M の名前が付いた M 人の人に 1 つずつ箱を渡そうとしています。
ただし、高橋君は以下の条件を満たすことができるように箱を買いたいです。
- 各 i = 1, 2, \ldots, M について、人 i には B_i 個以上のお菓子が入った箱を渡す
1 人に 2 個以上の箱を渡すことや同じ箱を複数人に渡すことはできないことに注意してください。
適切に箱を M 個買うことで条件を満たすことができるか判定し、条件を満たすことができる場合は高橋君が支払う金額の合計の最小値を求めてください。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
適切に箱を M 個買うことで条件を満たすことができる場合は高橋君が支払う金額の合計の最小値を出力せよ。そうでない場合は -1 を出力せよ。
入力例 1
4 2 3 4 5 4 1 4
出力例 1
7
高橋君は箱 1, 4 を買い、箱 1 を人 1、箱 4 を人 2 に渡すことで条件を満たすことができます。
このとき高橋君が支払う金額の合計は 7 円であり、支払う金額が 7 円未満のときは条件を満たすことはできないため、7 を出力します。
入力例 2
3 3 1 1 1 1000000000 1000000000 1000000000
出力例 2
-1
入力例 3
7 3 2 6 8 9 5 1 11 3 5 7
出力例 3
19
Score : 350 points
Problem Statement
A souvenir shop at AtCoder Land sells N boxes.
The boxes are numbered 1 to N, and box i has a price of A_i yen and contains A_i pieces of candy.
Takahashi wants to buy M out of the N boxes and give one box each to M people named 1, 2, \ldots, M.
Here, he wants to buy boxes that can satisfy the following condition:
- For each i = 1, 2, \ldots, M, person i is given a box containing at least B_i pieces of candy.
Note that it is not allowed to give more than one box to a single person or to give the same box to multiple people.
Determine whether it is possible to buy M boxes that can satisfy the condition, and if it is possible, find the minimum total amount of money Takahashi needs to pay.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
If it is possible to buy M boxes that can satisfy the condition, print the minimum total amount of money Takahashi needs to pay. Otherwise, print -1.
Sample Input 1
4 2 3 4 5 4 1 4
Sample Output 1
7
Takahashi can buy boxes 1 and 4, and give box 1 to person 1 and box 4 to person 2 to satisfy the condition.
In this case, he needs to pay 7 yen in total, and it is impossible to satisfy the condition by paying less than 7 yen, so print 7.
Sample Input 2
3 3 1 1 1 1000000000 1000000000 1000000000
Sample Output 2
-1
Sample Input 3
7 3 2 6 8 9 5 1 11 3 5 7
Sample Output 3
19