Surprise Party

Totos and Annoula's friends are impressed by their hard work and decide to relax them by organizing a surprise party. They start writing a list of items needed to make the party as fun as possible, along with a value indicating the importance of each item for the party, i.e., the cost incurred if that item is missing from the party.

The ~K~ friends decide to divide the ~N~ items from the list among themselves in sequence, so that each friend is responsible for bringing a continuous segment of items. However, recognizing that there's always a chance someone might forget to bring an item-and the more items someone is responsible for, the more likely they are to forget something-the friends want to ensure that the total estimated cost of potential missing items is minimized.

More formally:

You are given positive integers:

• ~N~, the number of items.
• ~K~, the number of friends.

You are also given a sequence ~A~ consisting of ~N~ positive integers ~A_1, A_2, ..., A_N~, which represent the cost of missing each item.

We need to divide the sequence ~A~ into ~K~ segments such that the sum of the estimated costs of each segment is minimized. The estimated cost of a segment of ~A~, consisting of the (consecutive) positions ~\{i, i+1, ..., j\}~ where ~i \le j~, is defined as:

$$\displaystyle \text{cost}(i, j) = \sum_{w=i}^j A_w \cdot (j - i + 1)$$

That is, we aim to find the minimum value of the expression:

$$\displaystyle \text{cost}(1, i_1-1) + \text{cost}(i_1, i_2-1) + \dots + \text{cost}(i_{K-1}, N)$$

where ~1 < i_1 < i_2 < ... < i_{K-1} \le N~.

Input Data (STDIN)

The ~1~st line contains two integers ~N~ and ~K~, separated by a space: the number of items and the number of friends, respectively.
The ~2~nd line contains ~N~ integers ~A_1, A_2, ..., A_N~, the cost of missing each item.

Output Data (STDOUT)

The output consists of a single line with one integer: the minimum total estimated cost.

Example

Input (STDIN)

6 3  
11 11 11 24 26 100

Output (STDOUT)

299

Example Explanation:
The first friend is responsible for the segment with the first three items, with an estimated cost of ~11 \cdot 3 + 11 \cdot 3 + 11 \cdot 3 = 99~. The second friend is responsible for the next two items, with an estimated cost of ~24 \cdot 2 + 26 \cdot 2 = 100~. The third friend is responsible for the last item, with an estimated cost of ~100 \cdot 1 = 100~.

Thus, the total estimated cost is ~99 + 100 + 100 = 299~, which is the minimum.

Constraints:

• ~1 \le K \le N \le 2000~
• ~1 \le A_i \le 10^9~

Subtasks:

• ~20\%~ of the points: ~K = 2~
• ~40\%~ of the points: ~K \le N \le 250~
• ~20\%~ of the points: ~A_1 \le A_2 \le ... \le A_N~, i.e., the elements of ~A~ are sorted in ascending order.
• ~20\%~ of the points: no additional constraints.