Maximizing Expression Value

You are given n numbers in a fixed order. Between every two consecutive numbers, you must place exactly one operator. In total, you have exactly n-1 operator slots. You are allowed to use exactly k multiplication operators and n-k-1 addition operators.

You can also add parentheses arbitrarily to change the evaluation order. Your task is to insert the operators in the fixed slots and add parentheses as needed so that the final value is maximized. In mathematical terms, if the numbers are \(a_1, a_2, \ldots, a_n\), you need to choose positions for the operators and determine a parenthesization to maximize the value of the expression.

Observation: In any valid expression, the additions group some consecutive numbers together and then these group sums are multiplied together. Hence, the problem can be reduced to partitioning the numbers into \(n-k\) segments, where the value of each segment is the sum of its numbers, and then taking the product of these sums.

Example:

For \(n=5\) and \(k=2\), the 5 numbers might be: 1, 2, 3, 4, 5. One possible way to add operators is:

[ 1 \times (2+3) \times (4+5)=45 ]

Here, the numbers are partitioned into 3 segments: \(\{1\}\), \(\{2,3\}\) and \(\{4,5\}\), and the product is \(1 \times 5 \times 9=45\). It can be verified that 45 is the maximum possible value for these inputs.

inputFormat

The first line contains two integers n and k, where n is the number of numbers and k is the number of multiplication operators you must use.

The second line contains n space-separated integers representing the numbers.

outputFormat

Output a single integer: the maximum value that can be achieved by inserting the operators and adding parentheses appropriately.

sample

5 2
1 2 3 4 5

45