배열 \(A = (A_1, A_2, ..., A_n)\)이 주어진다.

그리고 다음 동작을 정확히 \(B\)번 수행할 수 있다.

• \(A_i = c\)인 모든 값들을 0으로 바꾼다.

위의 동작을 정확히 \(B\)번 수행한 후, 가능한 배열 \(A\)의 합 중 최솟값을 구하시오.

입력

첫 번째 줄에 배열 \(A\)의 길이 \(n\)과 동작의 시행횟수 \(B\)가 입력으로 들어온다.

두 번째 줄에 \(A_1, A_2, ..., A_n\)이 입력으로 들어온다.

출력

\(B\)번의 동작 이후, 가능한 배열 \(A\)의 합 중 최솟값을 출력한다.

제한

• 입력은 모두 정수

• \(1 \le B \le n \le 300,000\)

• \(1 \le A_i \le 10^9\)

예제 1 설명

먼저 \(A_i = 1\) 인 모든 값들을 0으로 바꾸면 배열은 다음과 같이 변한다 : \((0, 0, 0, 0, 0, 7, 2, 2, 3, 4)\)

그리고 \(A_i = 7\)인 모든 값들을 0으로 바꾸면 배열은 다음과 같이 변한다 : \((0, 0, 0, 0, 0, 0, 2, 2, 3, 4)\)

그러면 남은 배열의 합은 \(2 + 2 + 3 + 4 = 11\) 이다.

예제 2 설명

이미 0이 된 \(A_i\)에 대해서도 동작을 수행할 수 있다.

서브태스크

번호
배점
제한

1
10
\(n \le 100\)

2
20
모든 \(A_i\)는 다른 값이다.

3
20
\(A_i \le 1000\)

4
50
추가 제한 없음

First line \(n\) and \(B\) (\(1 \le B \le n \le 300000\)). Second line \(A_1, \dots, A_n\) (\(1 \le A_i \le 10^9\)).

Print the minimum possible sum.

riseoj 작성

출처 Online Judge > GoldOJ