Informatica Online Judge

  박스와 공 [2110 / 083E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 12


The Champion of this Problem (C++) : gs16106 - 13ms / 690byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 최지원)]

Background

지원이는 $n$개의 서로다른 박스가 있다. 첫번째 박스에는 $n$종류의 서로다른 색의 공들이 들어있다.

지원이는 이상한 게임를 할 것이다. 그는 모든 $i$($1$≤$i$≤$n$)번째 상자에 모든 $i$색 공들을 넣고 싶어한다.

지원이는 각 턴마다 다음과 같은 일을 반복할 것이다.

------------------------------------------------------------------------------------------
1. 비어있지 않은 아무 상자를 골라 모든 공을 뺀다.
2. $k$($1$≤$k$≤$m$)개의 비어있는 상자를 고르고, $1$에서 뺀 공들을 분류해 각각의 상자에 넣는다.($1$≤$k$≤$n$)
------------------------------------------------------------------------------------------

1단계에서 뺀 공의 개수가 각 턴의 페널티일 때, 이 게임의 페널티는 모든 턴의 페널티의 합이다.

이 게임의 최소 페널티를 출력해야한다.

Input

첫 줄에 $n$($1≤n≤200,000$), $m$($1≤m≤n$)이 입력된다.

둘째 줄에 $n$개의 정수 $a_1, a_2, ..., a_n$ ($1≤a_i≤10^9$)가 입력된다. $a_i$는 $i$색의 공의 개수이다.

Output

이 게임의 최소 페널티를 출럭한다.

IO Example

입력
3 3
1 2 3

출력
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]