记录编号	251103	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	4.525 s
提交时间	2016-04-16 21:13:28	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int s[20];
int n,pr;
bool gp()
{
	if(s[14]!=2) return 0;
	if(s[3]!=0) return 0;
	if(s[5]!=2) return 0;
	if(s[7]!=2) return 0;
	if(s[8]!=0) return 0;
	if(s[11]!=1) return 0;
	if(s[12]!=2) return 0;
	return  1;
}
void gpr()
{
	for(int i=1;i<=15;++i)
	    if(s[i])
	        printf("%d %d\n",i,s[i]);
	puts("____________________");
}
void g(int a,int s,int d);
void gpt(int a,int ss,int d,int e,int hv)
{
	if(hv==2)
	{
		g(a,ss,d);
		return;
	}
	if(e>=16)
	    return;
	if(s[e]>0)
	{
		s[e]--;
		gpt(a,ss,d,e+1,hv+1);
		s[e]++;
	}
	gpt(a,ss,d,e+1,hv);
}
void gde(int a,int ss,int d,int e,int hv)
{
	/*if(ss==1&&gp()&&hv==0&&e==4)
	{
		printf("E%d %d\n",e,s[e]);
		gpr();
	}*/
	if(hv==2)
	{
		g(a,ss,d);
		return;
	}
	if(e>=16)
	    return;
	if(s[e]>=2)
	{
		s[e]-=2;
		gde(a,ss,d+2,e+1,hv+1);
		s[e]+=2;
	}
	gde(a,ss,d,e+1,hv);
}
void g(int a,int ss,int d)
{
	/////////
	/*bool pp=0;
	if(ss==4&&gt())
	{
		printf("noip%d ",d);
	    pp=1;
	}*/
	////////////
	if(ss>=pr)
	    return;
	if(d==n)
	{
		if(ss<pr)
			pr=ss;
		return;
	}
	if(a==16)
	    return;
	for(int i=a;i<=15;i++)
		if(s[i]>0)
		{
				//if(ss==0&&gp()&&i==8)
			//	    printf("S%d\n",s[3]);
			if(s[i]==4)//炸弹
			{
				s[i]=0;
				g(i+1,ss+1,d+4);
				gpt(i,ss+1,d+6,2,0);//带普通的2张牌
				gde(i,ss+1,d+4,2,0);//带对2
				s[i]=4;
			}
			s[i]--;
			g(i,ss+1,d+1);
			s[i]++;
			if(s[i]>=2)
			{
				s[i]-=2;
				g(i,ss+1,d+2);
				s[i]+=2;
			}
			if(s[i]>=3)
			{
				s[i]-=3;
				g(i,ss+1,d+3);//不带一
				for(int j=2;j<=15;j++)
				{
					if(s[j]>0&&j!=i)
					{
						s[j]--;//带一
				    	g(i,ss+1,d+4);
				    	s[j]++;
				    	if(s[j]>=2)//带二
				    	{
							s[j]-=2;
							g(i,ss+1,d+5);
							s[j]+=2;
				    	}
					}
				}
				s[i]+=3;
			}
			if(i==2)
			    continue;
			if(i<=10)//单顺子
			{
				int p=0;
				int j=i;
				for(;j<=14&&s[j]>0;j++)
				{
					p++;
					s[j]--;
					if(p>=5)
					{
					    g(i,ss+1,d+p);
					}
				}
				--j;
				for(j;j>=i;j--)
				    s[j]++;
			}
			if(i<=12)//双顺子
			{
				int p=0;
				int j=i;
				for(;j<=14&&s[j]>=2;j++)
				{
					p+=2;
					s[j]-=2;
					if(p>=6)
					    g(i,ss+1,d+p);
				}
				--j;
				for(;j>=i;j--)
				    s[j]+=2;
			}
			if(i<=12)//三顺子
			{
				int p=0;
				int j=i;
				for(;j<=14&&s[j]>=3;j++)
				{
					p+=3;
					s[j]-=3;
					if(p>=9)
					    g(i,ss+1,d+p);
				}
				--j;
				for(;j>=i;j--)
				    s[j]+=3;
			}
		}
}
inline void gmain()
{
	pr=0x3fffffff;
	for(int i=1;i<=15;i++)
	    s[i]=0;
	for(int i=1;i<=n;i++)
	{
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		if(aa==1)
		    s[14]++;
		else
		{
			if(aa==0)
			    s[15]++;
			else
			    s[aa]++;
		}
	}
	g(2,0,0);
	printf("%d\n",pr);
}
int main()
{
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	int t;
	scanf("%d%d",&t,&n);
	while(t--)
	{
	    gmain();
	}
	/*getchar();
	getchar();*/
	//while(1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}