时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个整数序列：\(A_1,A_2,…,A_n\)，现在需要把这个数按原来的顺序分成 \(m\) 组，每组包含若干连续的项，每组的代价为定义为：该组内所有数的和。
　　那么该如何分组，才能让每组的代价的乘积最大。

【输入格式】

　　第 1 行是 \(n\) 和 \(m\)；
　　第 2 行有 \(n\) 个整数，第 \(i\) 个数为 \(A_i\)。

【输出格式】

　　一个整数，表示最大的乘积。

【输入输出样例1】

　Input

6 2
1 0 3 2 1 4

　Output

30

【数据限制】

　　\(n≤1000,m≤10\)
　　\(0≤A_i≤10\)

【来源】

　Mr.he