NOIP2015 LANDLORDS

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n, ans, p[15], L[4];

void Dfs(int dep, int k) {
	if(!k) {
		ans = min(ans, dep);
		return ;
	}
	if(dep >= ans) return ;
	for(int i = 0; i < 13; i++) if(p[i] == 3) { 
			p[i] -= 3;
			Dfs(dep+1, k-3); 
			for(int j = 0; j < 15; j++) if(p[j] && j!=i) { 
					p[j]--;
					Dfs(dep+1, k-4);
					if(p[j]) {
						p[j]--;   
						Dfs(dep+1, k-5);
						p[j]++;
					}
					p[j]++;
				}
			p[i] += 3;
		}
	for(int i = 0; i < 13; i++) if(p[i] == 4) { 
			p[i] -= 4;
			Dfs(dep+1, k-4); 
			for(int j = 0; j < 13; j++) if(p[j]) { 
					p[j]--;
					for(int t = j; t < 13; t++) if(p[t]) {
							p[t]--;
							Dfs(dep+1, k-6);
							p[t]++;
						}
					p[j]++;
				}
			for(int j = 0; j < 13; j++) if(p[j]>1) { 
					p[j] -= 2;
					for(int t = j; t < 13; t++) if(p[t]>1) {
							p[t] -= 2;
							Dfs(dep+1, k-8);
							p[t] += 2;
						}
					p[j] += 2;
				}
			p[i] += 4;
		}
	for(int i = 0; i < 13; i++) {
		dep += (p[i]/2) + (p[i]%2); 
		if(dep >= ans) return ;
	}
	if(p[13] == 1 || p[14] == 1) dep++;
	ans = min(ans, dep); 
}

void Solve(int dep, int k) {
	if(!k) {
		ans = min(ans, dep);
		return ;
	}
	if(dep >= ans) return ;
	for(int t = 1; t <= 3; t++) 
		for(int i = 0; i < 13-L[t]; i++) if(p[i] >= t) {
				int len = 1, j;
				for(j = i+1; j < 12; j++) if(p[j] < t) break;
					else len++;
				if(len < L[t]) {
					i = j;
					continue;
				}
				for(j = i; j < i+len; j++) p[j] -= t;
				for(j = len; j >= L[t]; j--) {
					Solve(dep+1,k-t*j);
					p[i+j-1] += t;
				}
				for(j = i; j < i+L[t]-1; j++) p[j] += t;
			}
	Dfs(dep, k);
}

int main() {
	int T;
	scanf("%d%d",&T,&n);
	L[1] = 5,L[2] = 3,L[3] = 2;
	while(T--) {
		memset(p, 0, sizeof(p));
		for(int i = 1; i <= n; i++) {
			int c, c2;
			scanf("%d%d",&c,&c2);
			if(c > 2) c -= 3;
			else if(!c) c = 12+c2;
			else c += 10;
			p[c]++;
		}
		ans = n;
		Solve(0, n);
		printf("%d\n", ans);
	}
	return 0;
}