E - Colorful T-Shirts Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 枚の T シャツが売られています。各 T シャツの色は 1 以上 10^9 以下の整数で表され、i 枚目の T シャツの色は c_i で価格は p_i 円です。

K 種類の色の T シャツを集めるには最小で何円必要ですか?

ただし、K 種類の色の T シャツを集めることが不可能な場合は -1 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq N+1
  • 1 \leq c_i,p_i \leq 10^9
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
c_1 c_2 \ldots c_N
p_1 p_2 \ldots p_N

出力

答えを(単位を除いて)出力せよ。


入力例 1

3 2
2 1 2
3 4 5

出力例 1

7

1 枚目と 2 枚目の T シャツを買うのが最適です。


入力例 2

3 3
2 1 2
3 4 5

出力例 2

-1

入力例 3

4 2
4 10 2 4
1 5 3 2

出力例 3

4

Score : 7 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A shop sells N T-shirts. The color of each T-shirt is represented as an integer between 1 and 10^9 (inclusive). The i-th T-shirt has a color of c_i and a price of p_i yen (Japanese currency).

What is the minimum amount of money needed to get T-shirts of K different colors?

If it is impossible to get T-shirts of K different colors, print -1.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq N+1
  • 1 \leq c_i,p_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
c_1 c_2 \ldots c_N
p_1 p_2 \ldots p_N

Output

Print the answer (as a single integer).


Sample Input 1

3 2
2 1 2
3 4 5

Sample Output 1

7

The optimal choice is to buy the first and second T-shirts.


Sample Input 2

3 3
2 1 2
3 4 5

Sample Output 2

-1

Sample Input 3

4 2
4 10 2 4
1 5 3 2

Sample Output 3

4