Guardians of the Lunatics

Time limit7sMemory limit512 MB

Summary

Split a row of L cells into at most G contiguous nonempty blocks, where a block of length k multiplies each member's craziness by k, to minimize the total cost.

Level: Hard8 of 10
Topics: Dynamic programming, Divide and conquer, Prefix sum, Greedy
Solved: No attempts yet

Problem

You assign the guards of a prison that holds the most dangerous criminals. The $L$ cells stand in one row and are numbered 1 to $L$ . Cell $i$ holds exactly one lunatic whose craziness level is $C_i$ .

One guard per lunatic would be ideal, but the budget pays for only $G$ guards. Decide which lunatics each guard watches so that the total risk of an escape is as small as possible.

Each guard watches a set of adjacent cells. A guard may be left with no cell at all. The risk $R_i$ that the lunatic in cell $i$ escapes is the product of the craziness level $C_i$ and the number of lunatics watched by the guard assigned to that cell. Adding up $R_i$ from $i = 1$ to $i = L$ gives the total risk $R$ .

Given $L$ lunatics and $G$ guards, find the minimum possible value of $R$ .

Input

The first line contains one integer $T$ , the number of test cases.

The first line of each test case contains two integers $L$ and $G$ separated by a space, the number of lunatics and the number of guards. Each of the next $L$ lines contains one integer, and the $i$ th of them is the craziness level $C_i$ of the lunatic in cell $i$ .

Constraints

$1 \leq T \leq 22$
$1 \leq L \leq 8000$
$1 \leq G \leq 800$
$1 \leq C_i \leq 10^9$

Output

For each test case, print the minimum possible value of the total risk $R$ on its own line.

Examples4

Example 1
Input
```
1
6 3
11
11
11
24
26
100
```
Expected output
```
299
```
Example 2
Input
```
1
1 1
7
```
Expected output
```
7
```
Example 3
Input
```
1
5 1
5
4
3
2
1
```
Expected output
```
75
```
Example 4
Input
```
1
4 10
5
3
9
1
```
Expected output
```
18
```