【Noip2015】斗地主

#include<bits/stdc++.h>
using namespace std;
int pai[20],T;
int n;
int ans;
void shunzi(int step);
void feiji(int step);
void liandui(int step);
int sanpai();
void chupai(int step){
    if (step>=ans)
        return;
    ans=min(ans,step+sanpai());
    feiji(step);
    shunzi(step);
    liandui(step);
}
void shunzi(int step){
    int l=0;
    for (int i=3;i<=13;i++){
        l=0;
        while (pai[i+l]>=1)
            l++;
        for (int j=l;j>=5;j--){
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]-1;
            chupai(step+1);
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]+1;
        }
    }
}
void feiji(int step){
    int l=0;
    for (int i=3;i<=13;i++){
        l=0;
        while (pai[i+l]>=3)
            l++;
        for (int j=l;j>=2;j--){
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]-3;
            chupai(step+1);
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]+3;
        }
    }
}
void liandui(int step){
    int l=0;
    for (int i=3;i<=13;i++){
        l=0;
        while (pai[i+l]>=2)
            l++;
        for (int j=l;j>=3;j--){
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]-2;
            chupai(step+1);
            for (int k=i;k<=i+j-1;k++)
                pai[k]=pai[k]+2;
        }
    }
}
int sanpai(){
    bool wangzha=false;
    if (pai[1]==2)
        wangzha=true;
    int zhangshu[5];
    memset(zhangshu,0,sizeof(zhangshu));
    for (int i=2;i<=14;i++)
        zhangshu[pai[i]]++;
    zhangshu[1]+=pai[1];
    int num=0;
    if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha==false)
        return zhangshu[1];
    if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha)
        return zhangshu[1]-1;
    //炸->3+1  *  4+2  +  3+1     step 2
    //
    while (!zhangshu[3]&&zhangshu[4]>=2&&zhangshu[1]==1&&zhangshu[2]==1){
        zhangshu[4]--;
        zhangshu[4]--;
        zhangshu[1]--;
        zhangshu[2]--;
        num=num+2;
    }
    //3->2+1   * 4+2 3+1 step 2
    while (!zhangshu[2]&&zhangshu[4]==1&&zhangshu[3]>=2&&zhangshu[1]==1){
        zhangshu[3]-=2;
        zhangshu[4]--;
        zhangshu[1]--;
        num+=2;
    }
    //3+4>2+1 3->2+1 * 4+2*2  1
    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
        while (zhangshu[4]&&zhangshu[3]&&zhangshu[2]){
            zhangshu[3]--;
            zhangshu[4]--;
            zhangshu[2]--;
            zhangshu[1]++;
            num++;
        }
    //
    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
        while (zhangshu[4]>=2&&zhangshu[3]>=2){
            zhangshu[3]-=2;
            zhangshu[4]-=2;
            num+=2;
        }
    //3+4>2+1  3->2+1 * 4+2*1 2
    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
        while (zhangshu[4]&&zhangshu[3]&&zhangshu[1]){
            zhangshu[1]--;
            zhangshu[3]--;
            zhangshu[4]--;
            zhangshu[2]++;
            num++;
        }
    //4+2*1
    while (zhangshu[4]&&zhangshu[1]>1){
        zhangshu[4]--;
        zhangshu[1]-=2;
        num++;
    }
    //4+2*2
    while (zhangshu[4]&&zhangshu[2]>1){
        zhangshu[4]--;
        zhangshu[2]-=2;
        num++;
    }
    //2->1+1 4+1+1
    while (zhangshu[4]&&zhangshu[2]){
        zhangshu[4]--;
        zhangshu[2]--;
        num++;
    }
    //3->1+2 *  3+1 3+2
    if (zhangshu[3]%3==0&&zhangshu[1]+zhangshu[2]<=1)
        while (zhangshu[3]>=3){
            zhangshu[3]-=3;
            num+=2;
        }
    //3+1
    while (zhangshu[3]&&zhangshu[1]){
        zhangshu[3]--;
        zhangshu[1]--;
        num++;
    }
    //3+2
    while (zhangshu[3]&&zhangshu[2]){
        zhangshu[3]--;
        zhangshu[2]--;
        num++;
    }
    //4->2 + 1*2   3+2 4+1*2
    while (zhangshu[4]>1&&zhangshu[3]){
        zhangshu[4]-=2;
        zhangshu[3]--;
        num+=2;
    }
    //4->2*2  3+2 3+2
    while (zhangshu[4]&&zhangshu[3]>1){
        zhangshu[4]--;
        zhangshu[3]-=2;
        num+=2;
    }
    //3->1+2  *  3+1  3+2
    while (zhangshu[3]>2){
        zhangshu[3]-=3;
        num+=2;
    }
    //4->2+2 * 4+2*2
    while (zhangshu[4]>1){
        zhangshu[4]-=2;
        num+=1;
    }
    if (wangzha==true&&zhangshu[1]>=2)
        return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4]-1;
    else 
        return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4];
}
int main(){
    scanf("%d%d",&T,&n);
    while (T--){
        ans=n;
        memset(pai,0,sizeof(pai));
        for (int i=1;i<=n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if (x==1){
                pai[14]++;
            }
            else if (x==0)
                pai[1]++;
            else 
                pai[x]++;
        }
        chupai(0);
        printf("%d\n",ans);
    }
    return 0;
}