#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<map>
using namespace std;
const int N=310,M=2005;
int n,k;
int s[N][N][2],dp[N][N][2],q[N],ans;
map<string,int> w;
map<string,int> c;
int main()
{
	freopen("merge_2016.in","r",stdin);
	freopen("merge_2016.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",&q[i]),s[i][i][q[i]]=1;
	for(int i=0;i<(1<<k);++i)
	{
		string state;
		for(int j=k-1;j>=0;--j)
			state.push_back(((i>>j)&1)+'0');
		cout<<state<<endl;
		scanf("%d%d",&c[state],&w[state]);
	}
	for(int l=1;l+k-1<=n;++l)//prework 
	{
		int r=l+k-1;
		string st;
		for(int i=l;i<=r;++i)
			if(s[i][i][0]) st.push_back('0');
			else st.push_back('1');
		s[l][r][c[st]]=1;
		dp[l][r][c[st]]=w[st];
	}
	for(int len=k+1;len<=n;++len)
	{
		for(int l=1;l+len-1<=n;++l)
		{
			int r=l+len-1;
			for(int x=l;x+len-k<=r;++x)
			{
				int y=x+len-k;
				if(!(s[x][y][0]||s[x][y][1])) continue;
				string ls="",rs="";
				for(int i=l;i<=x-1;++i) ls.push_back((char)q[i]+'0');
				for(int i=y+1;i<=r;++i) rs.push_back((char)q[i]+'0');
				if(s[x][y][0])
				{
					string str=ls+"0"+rs;
					int f=c[str];
					s[l][r][f]=1;
					dp[l][r][f]=max(dp[l][r][f],dp[x][y][0]+w[str]);
				}
				if(s[x][y][1])
				{
					string str=ls+"1"+rs;
					int f=c[str];
					s[l][r][f]=1;
					dp[l][r][f]=max(dp[l][r][f],dp[x][y][1]+w[str]);
				}
			}
			ans=max(ans,max(dp[l][r][0],dp[l][r][1]));
		}
	 } 
	 printf("%d\n",ans);
	return 0;
}