Lawrence of Arabia

T. E. Lawrence was a British officer in World War I who led Arab fighters in guerrilla strikes against the Ottoman Empire, targeting its railroads. You must help Lawrence use his limited resources to do the most damage.

The rail line is completely linear: no branches and no spurs. British Intelligence assigns each depot a Strategic Value, an integer from 1 to 5. A depot has value only through its connections: the Strategic Value of the whole railroad is the sum, over every pair of depots that are still connected (directly or indirectly) along the line, of the product of their Strategic Values. For example:

This railroad's Strategic Value is 4 × 5 + 4 × 1 + 4 × 2 + 5 × 1 + 5 × 2 + 1 × 2 = 49.

Lawrence has resources for a limited number of attacks. He cannot attack the depots themselves (they are too well defended); each attack destroys the rail line between two adjacent depots, out in the desert. If he attacks the line above right in the middle:

the remaining Strategic Value is 4 × 5 + 1 × 2 = 22. If instead he attacks between the depots valued 4 and 5:

the remaining Strategic Value is 5 × 1 + 5 × 2 + 1 × 2 = 17, which is his best option here.

Given a railroad and the number of attacks Lawrence can make, find the smallest Strategic Value he can leave the railroad with.

The input contains several data sets. Each data set begins with a line of two integers $N$ and $M$: $N$ is the number of depots on the railroad ($1 \le N \le 500$) and $M$ is the number of attacks Lawrence has resources for ($0 \le M < N$). The next line contains $N$ integers, each from 1 to 5, giving the Strategic Value of each depot in order. The end of input is marked by a line containing two space-separated 0s.

For each data set, print a single integer: the smallest Strategic Value that Lawrence can leave the railroad with after making his attacks. Print each integer on its own line, with no blank lines between outputs.