记录编号	210832	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.235 s
提交时间	2015-11-29 11:05:51	内存使用	0.29 MiB

#define Rep for(int i=0;i<14;i++)

#define MAXN 20UL
#define MAXS 180UL

#include <cstdio>
#include <cstring>

int s[MAXN],t,n,mk[MAXS][MAXN],Ans,cnt;

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}

inline void Check(int t,int len,int num){
	for(int i=t,j=1;j<=len;j++,i++){
		if(i==14) i=1;
		if(s[i]<num) return;
	}
	++cnt;
	for(int i=t,j=1;j<=len;j++,i++){
		if(i==14) i=1;
		mk[cnt][i]=num;
	}
	return;
}

inline void ReadIn(){
	memset(s,0,sizeof(s));
	memset(mk,0,sizeof(mk));
	cnt=0;
	for(int i=1,a,c;i<=n;i++){
		a=in(),c=in();
		s[a]++;
	}
	for(int len=12;len>=2;len--) for(int i=3,r=15-len;i<=r;i++)
		Check(i,len,3);
	for(int len=12;len>=3;len--) for(int i=3,r=15-len;i<=r;i++)
		Check(i,len,2);
	for(int len=12;len>=5;len--) for(int i=3,r=15-len;i<=r;i++)
		Check(i,len,1);
	Rep if(s[i]>=4){
		for(int j=0;j<14;j++){
			if(i==j||(!s[j])) continue;
			for(int k=j+1;k<14;k++){
				if(i==k||(!s[k])) continue;
				++cnt;
				mk[cnt][i]=4;
				mk[cnt][j]=mk[cnt][k]=1;
			}
		}
		for(int j=0;j<14;j++){
			if(i==j||s[j]<2) continue;
			for(int k=j+1;k<14;k++){
				if(i==k||s[k]<2) continue;
				++cnt;
				mk[cnt][i]=4;
				mk[cnt][j]=mk[cnt][k]=2;
			}
		}
	}
	Rep if(s[i]>=3){
		for(int j=1;j<14;j++){
			if(i==j||s[j]<2) continue;
			++cnt;
			mk[cnt][i]=3;
			mk[cnt][j]=2;
		}
		for(int j=0;j<14;j++){
			if(i==j||(!s[j])) continue;
			++cnt;
			mk[cnt][i]=3;
			mk[cnt][j]=1;
		}
	}
	return;
}

inline int Rest(){
	int p=0;
	Rep if(s[i]) p++;
	return p;
}

inline void Div(int p,int num){
	Rep s[i]-=mk[p][i]*num;
	return;
}

inline void Res(int p){
	Rep s[i]+=mk[p][i];
	return;
}

inline int Min(int a,int b){
	return a<b?a:b;
}

inline int Cal(int p){
	int temp=n;
	Rep if(mk[p][i]){
		temp=Min(temp,s[i]/mk[p][i]);
	}
	return temp;
}

int dfs(int p,int step){
	if(step>=Ans) return 50L;
	int rest=Rest(),temp_ans,num;
	if(p>cnt) return rest;
	if(!rest) return 0;
	if(rest+step<Ans) Ans=rest+step;
	temp_ans=rest;
	num=Cal(p);
	Div(p,num);
	for(int i=num,tmp;i>=0;i--){
		if(i!=num) Res(p);
		tmp=dfs(p+1,step+i);
		if(tmp+i<temp_ans) temp_ans=tmp+i;
		if(step+temp_ans<Ans) Ans=step+temp_ans;
	}
	return temp_ans;
}

inline void Work(){
	Ans=Rest();
	printf("%d\n",dfs(1,0));
	return;
}

int main(){
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
	t=in(),n=in();
	for(int i=1;i<=t;i++) ReadIn(),Work();
	return 0;
}