This problem can be solved by using DP (dynamic programming) in O(K*N²) time.

At first, let's consider the case K = 1. After failed breaking an egg with x taps, she should tap exactly x times next egg if A_i correspongind to next egg is no less than x. So, one of the worst-case is that she firstly tries to break all of the eggs whose A_i is greater than x, then she tries to break the egg which has greatest A_i among the untried eggs. Of course, x should be one of A_i. Therefore, the answer for the case K = 1 is the minimum value of A_a * (1 + number of eggs whose A_i is greater than A_a).

In the case K > 1, she should do the similar thing repeatly. For simplicity, we sort A_i, at first, so that A_i ≤ A_i+1. After successful breaking the j-th egg, if she try to break the i-th egg (i < j), the number of taps for the worst-case is A_i * (j - i) + A_j * (N + 1 - j). You can prove that above number of taps is equal to the number of taps for the worst-case when she tries to break the j-th egg after successful breaking the i-th egg. Therefore, we can assume x₁ > x₂ > ... > x_K, where her k-th target is the x_k-th egg.

This problem can be solved by using a simple DP now. Let dp[last][broken] be the number of taps for the worst-case after successful breaking the (x_broken = last)-th egg. You can find the equation among dp[last][broken] in the following problem setter's code.