The Dimension Rift Calculator | Coding Challenges

Description

Hard

The Dimension Rift Calculator

A multiverse explorer can travel between dimensions. There are n dimensions numbered 1 to n. The explorer starts in dimension 1 and wants to reach dimension n.

From dimension i, the explorer can jump to dimension j if i < j. However, each jump has an energy cost equal to (j - i) * stability[i] where stability[i] is the instability factor of dimension i.

Additionally, the explorer can only make at most k jumps total.

Find the minimum energy required to reach dimension n from dimension 1 using at most k jumps.

Input Format

The first line contains two integers n and k. The second line contains n space-separated integers representing the stability values.

Output Format

Print the minimum energy required.

Examples

Example 1

Input

4 2 1 2 3 1

Output

ExplanationJump 1->4 costs (4-1)*1 = 3. Or jump 1->2 costs 1*1=1, then 2->4 costs 2*2=4, total 5. Best is 1->3->4: (3-1)*1 + (4-3)*3 = 2+3 = 5. Actually 1->4 direct is (4-1)*1=3.

Example 2

Input

3 1 10 1 1

Output

ExplanationOnly one jump allowed: 1->3 costs (3-1)*10 = 20.

Constraints

•

2 ≤ n ≤ 5000

•

1 ≤ k ≤ n-1

•

1 ≤ stability[i] ≤ 1000

Code

Error

Case 1

Case 2

Input

4 2 1 2 3 1

Output

No output

Expected