55pts求调，悬5关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000],f[20][20][20];
signed main()
{
	memset(f,-1,sizeof(f));
	long long n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>f[i][i][0];
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<n;j++)
			f[i][j][0]=f[i][j-1][0]+f[j][j][0];
	for(int len=2;len<=n;len++) //长度 
	{
		for(int l=1;l+len-1<=n;l++) //左端点 
		{
			int r=l+len-1; //右端点 
			for(int k=1;k<=min(m,len-1);k++) //乘号个数 
			{
				for(int q=0;q<=k;q++) //乘号个数断点 左边取q个，右边取k-q个 
					for(int w=l;w<r;w++) //转移断点 
						if(f[l][w][q]!=-1 && f[w+1][r][k-q]!=-1)
						{
							f[l][r][k]=max(f[l][r][k],f[l][w][q]+f[w+1][r][k-q]);
						}
				for(int q=0;q<k;q++)
					for(int w=l;w<r;w++)
					{
						if((f[w+1][r][k-q-1]!=-1 && f[l][w][q]!=-1))
							f[l][r][k]=max(f[l][r][k],f[l][w][q]*f[w+1][r][k-q-1]);
						if((f[l][w][q-1]!=-1 && f[w+1][r][k-q]!=-1))
							f[l][r][k]=max(f[l][r][k],f[l][w][q-1]*f[w+1][r][k-q]);
					}
//				cout<<l<<" "<<r<<" "<<k<<":"<<f[l][r][k]<<"\n"; 
			}
		}
	}
	cout<<f[1][n][m]<<endl;
	return 0;
}
/*
5 4
0 0 1 0 0
*/