题目描述

给出 $N$ 个数字，不改变它们的相对位置，在中间加入若干个乘号和若干个加号，（括号随便加）使最终结果尽量大。

因为乘号和加号一共就是 $N-1$ 个了，所以恰好每两个相邻数字之间都有一个符号。

例如：$N=5$，$K=2$，$5$ 个数字分别为 $1$、$2$、$3$、$4$、$5$，可以加成：

输入格式

第一行为两个有空格隔开的整数，表示 $N$ 和 $K$（$K$ 表示至多加入的乘号的个数，不一定要求刚好加 $K$ 个乘号）。

第二行为 $N$ 个用空格隔开的数字（每个数字在 $0$ 到 $9$ 之间）。

输出格式

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

5 2
1 2 3 4 5

120

数据规模与约定

$2\le N\le15$，$0\le K\le N-1$。