记录编号	281544	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	1.326 s
提交时间	2016-07-11 20:41:36	内存使用	5.01 MiB

//HAOI 2016 T4
//by Cydiater
//2016.7.11
#include <iostream>
#include <cstring>
#include <string>
#include <iomanip>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#include <cmath>
#include <cstdio>
using namespace std;
#define up(i,j,n) 	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define FILE "merge_2016"
#define ll long long
const int oo=0x3f3f3f3f;
const int MAXN=305;
inline ll read(){
	char ch=getchar();ll x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll N,K,f[MAXN][MAXN][2],c[MAXN],v[MAXN],a[MAXN],g[MAXN][1<<9],now,tmp[3],ans[MAXN];
namespace solution{
	void init(){
		N=read();K=read();
		memset(f,-1,sizeof(f));
		up(i,1,N){a[i]=read();f[i][i][a[i]]=0;}
		up(i,0,(1<<K)-1)c[i]=read(),v[i]=read();
	}
	void slove(){
		down(i,N-K+1,1){
			memset(g,-1,sizeof(g));
			now=1;g[i][0]=f[i][i][0];g[i][1]=f[i][i][1];
			up(j,i+1,N){
				up(s,0,(1<<now)-1)if(g[j-1][s]>=0)for(int k=j;k<=N;k+=K-1){
					if(f[j][k][0]>=0)g[k][s<<1]=max(g[k][s<<1],g[j-1][s]+f[j][k][0]);
					if(f[j][k][1]>=0)g[k][s<<1|1]=max(g[k][s<<1|1],g[j-1][s]+f[j][k][1]);
				}
				if(++now==K){
					tmp[0]=tmp[1]=-1;
					up(k,0,(1<<now)-1)if(g[j][k]>=0)tmp[c[k]]=max(tmp[c[k]],v[k]+g[j][k]);
					f[i][j][1]=g[j][1]=tmp[1];
					f[i][j][0]=g[j][0]=tmp[0];
					now=1;
				}
			}
		}
	}
	void output(){
		up(i,1,N)for(int j=i;j<=N;j+=K-1)ans[j]=max(ans[j],ans[i-1]+max(f[i][j][1],f[i][j][0]));
		printf("%lld\n",ans[N]);
	}
}
int main(){
	//freopen("input.in","r",stdin);
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	init();
	slove();
	output();
	return 0;
}