P1388 Expression

Given $n$ numbers, without changing their relative order, insert $k$ multiplication signs and $(n-k-1)$ plus signs between them. Parentheses can be added arbitrarily to maximize the final result. Since the total number of operators is $n-1$, there is exactly one operator between every pair of adjacent numbers. For example: When $n=5$, $k=2$, and the $5$ numbers are $1$, $2$, $3$, $4$, $5$, you can form: $$1\times 2\times(3+4+5)=24$$ $$1\times(2+3)\times(4+5)=45$$ $$(1\times2+3)\times(4+5)=45$$ $$\ldots\ldots$$

The first line contains two integers separated by a space, denoting $n$ and $k$. The second line contains $n$ space-separated integers $a_i$, representing the given numbers.

Output a single line containing one integer, the maximum possible result.

#### Constraints - For $100\%$ of the testdata, it is guaranteed that $2\le n\le15$, $0\le k\lt n$, $0 \leq a_i \leq 9$, and the answer is less than $2^{31}$. Translated by ChatGPT 5