Description

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:

Input Format

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 Format

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

5 2
1 2 3 4 5

120

Hint

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