Problem Description

In the Takahashi Kingdom, there are $ N+1 $ towns numbered from $ 0 $ to $ N $.

Takahashi, who lacks exercise, decided to walk from town $ 0 $ to town $ N $. Takahashi has $ K $ empty plastic bottles.

When Takahashi is in town $i (0 \leq i < N)$, he can perform the following two actions:

• Pay $ A_i $ yen to fill one empty plastic bottle with water. This action can be performed any number of times.
• Drink one filled plastic bottle dry and turn it into an empty bottle. Takahashi moves from town $ i $ to town $ i+1 $.

Find the minimum amount of money Takahashi needs to reach town $ N $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_0 $ $ A_1 $ $ ... $ $ A_{N-1} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

6 3
2 7 1 8 2 8

Sample Output #1

9

Sample Input #2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

Sample Output #2

26

Notes/Hints

Constraints

• $1 \leq K \leq N \leq 10^{5}$
• $1 \leq A_i \leq 10^{9}$
• All given inputs are integers

Sample Explanation 1

• Fill 2 bottles with water in town $ 0 $
• Move to town $ 1 $
• Move to town $ 2 $
• Fill 3 bottles with water in town $ 2 $
• Move to town $ 3 $
• Move to town $ 4 $
• Fill 1 bottle with water in town $ 4 $
• Move to town $ 5 $
• Move to town $ 6 $
• By acting this way, it is possible to arrive at town $ 6 $ for $ 9 $ yen, which is the optimal solution.

见题面 Input 部分

见题面 Output 部分