/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。
以下の操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。
- 整数 x を選ぶ。A_i = x なる各 i について A_i の値を 0 に置き換える。
制約
- 1 \leq K \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 2 7 2 7 2 2 9
出力例 1
6
はじめ、A = (7, 2, 7, 2, 2, 9) です。
x = 9 として操作を行うと、A = (7, 2, 7, 2, 2, 0) となります。
次に x = 7 として操作を行うと、A = (0, 2, 0, 2, 2, 0) となります。
このとき、A の各要素の和は 0 + 2 + 0 + 2 + 2 + 0 = 6 となります。
入力例 2
8 6 1 2 3 4 1 2 3 4
出力例 2
0
入力例 3
10 2 3 3 4 1 1 3 3 1 5 1
出力例 3
8
Score : 300 points
Problem Statement
You are given an integer sequence A = (A_1, A_2, \ldots, A_N).
Find the minimum possible sum of all elements of A after performing the following operation exactly K times.
- Choose an integer x. For each i such that A_i = x, replace the value of A_i with 0.
Constraints
- 1 \leq K \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
6 2 7 2 7 2 2 9
Sample Output 1
6
Initially, A = (7, 2, 7, 2, 2, 9).
Performing the operation with x = 9 gives A = (7, 2, 7, 2, 2, 0).
Next, performing the operation with x = 7 gives A = (0, 2, 0, 2, 2, 0).
At this point, the sum of all elements of A is 0 + 2 + 0 + 2 + 2 + 0 = 6.
Sample Input 2
8 6 1 2 3 4 1 2 3 4
Sample Output 2
0
Sample Input 3
10 2 3 3 4 1 1 3 3 1 5 1
Sample Output 3
8