Zayin and the Monsters

Zayin is a wizard who battles monsters. He is about to face ( n ) monsters standing in a row, where the ( i)-th monster has a health value of ( a_i ). However, due to a mysterious force, Zayin cannot choose which monster to attack directly. In fact, there is a permutation ( p ) of ( {1,2,\dots,n} ) such that when Zayin intends to attack the ( i)-th monster, he actually attacks the ( p_i )-th monster.

On each attack, Zayin may choose an integer ( k ) in the range ( [1,n] ). This causes the health of the monster at position ( p_k ) to decrease by 1. A monster dies when its health becomes less than or equal to 0.

Zayin does not know the permutation ( p ) and cannot see the remaining health of each monster – he only learns after each attack whether a monster has died. Under an optimal (adaptive) strategy, he wishes to know the maximum number of attacks that might be needed to kill ( m ) monsters in the worst case.

Analysis: Although Zayin can choose which index to attack, the adversary controlling the permutation ( p ) will assign the given health values ( a_1, a_2, \dots, a_n ) to the positions in a way that delays deaths as much as possible. Suppose Zayin decides to attack a set of ( k ) indices repeatedly (with ( m \le k \le n )) until at least ( m ) monsters among them are dead. If each chosen index is attacked in every round, after ( t ) rounds each such monster has received ( t ) attacks. A monster dies when ( t \ge h ) where ( h ) is its health. Because the adversary can assign the health values arbitrarily among the indices, the worst case is achieved when, for the selected ( k ) indices, the adversary assigns the ( k ) largest health values (from the given multiset) in increasing order. In this case, the ( m)-th death among these ( k ) positions occurs when ( t ) is at least the ( m )-th smallest value in this chosen set. By sorting ( a_1, a_2, \dots, a_n ) in increasing order as ( a_{(1)} \le a_{(2)} \le \dots \le a_{(n)} ), if we assign the ( k ) chosen positions the values ( a_{(n-k+1)}, a_{(n-k+2)}, \dots, a_{(n)} ) then the ( m)-th death will occur in round ( t = a_{(n-k+m)} ). Since each round uses ( k ) attacks, the total number of attacks is ( k \cdot a_{(n-k+m)} ). Zayin can choose ( k ) (with ( m \le k \le n )) to minimize the total number of attacks in the worst-case scenario.

Thus, the answer is given by: [ \min_{k=m}^{n} ; \Bigl( k \cdot a_{(n-k+m)} \Bigr), ] where ( a_{(i)} ) denotes the ( i)-th smallest value among ( a_1, a_2, \dots, a_n ).

inputFormat

The first line contains two integers \( n \) and \( m \) (\( 1 \le m \le n \le 10^5 \)).

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \) (\( 1 \le a_i \le 10^9 \)).

outputFormat

Output a single integer, which is the maximum number of attacks needed to kill \( m \) monsters under the optimal strategy.

sample

3 1
1 2 5

3