题目描述

给出 $n$ 个数字，不改变它们的相对位置，在中间加入 $k$ 个乘号和 $(n-k-1)$ 个加号，括号随便加，使最终结果尽量大。因为乘号和加号一共就是 $n-1$ 个了，所以恰好每两个相邻数字之间都有一个符号。例如：

$n=5$，$k=2$，$5$ 个数字分别为 $1$，$2$，$3$，$4$，$5$，可以加成：

输入格式

输入的第一行为两个用空格隔开的整数，分别表示表示 $n$ 和 $k$。

第二行为 $n$ 个用空格隔开的整数 $a_i$，代表给出的数字。

输出格式

输出文件仅一行包含一个整数，表示要求的最大的结果。

5 2
1 2 3 4 5

120

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $2\le n\le15$，$0\le k\lt n$，$0 \leq a_i \leq 9$，答案小于 $2^{31}$。