Description
Dr. X is a biologist, who likes rabbits very much and can do everything for them. 2012 is coming, and Dr. X wants to take some rabbits to Noah's Ark, or there are no rabbits any more.
A rabbit's genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only 'A', 'G', 'T', 'C'. There is no doubt that Dr. X had a in-depth research on the rabbits' genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.
We can make a example, if a rabbit has gene segment "ATG", its W would plus 4; and if has gene segment "TGC", its W plus -3. So if a rabbit's gene string is "ATGC", its W is 1 due to ATGC contains both "ATG"(+4) and "TGC"(-3). And if another rabbit's gene string is "ATGATG", its W is 4 due to one gene segment can be calculate only once.
Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit.
 
Input
There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10),l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits' genes.
The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit's W.
 
Output
For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output "No Rabbit after 2012!".
 
Sample Input

      
      
      
      

       
       
       
       2 4
ATG 4
TGC -3

1 6
TGC 4

4 1
A -1
T -2
G -3
C -4 
      
      
      
      

 
Sample Output

      
      
      
      

       
       
       
       4
4
No Rabbit after 2012!


         
         
      
      
      
      

Hint

 case 1：we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc. case 2：we can find a rabbit whose gene string is TGCTGC(4), or TGCCCC(4) etc. case 3：any gene string whose length is 1 has a negative W. 
         

 
이번 컨디션 압축 dp는 너무 어려워요. QAQ 모양 압도도 자기 dp 중에 제일 못해요.
제목: DNA 서열에서 전체적인 공헌 값을 정할 수도 있고 마이너스할 수도 있으며 n 피드 문자열이 표시할 수 있는 m 길이의 문자열의 최대 값을 구하고 - 1 단독 출력
이 문제를 풀면 반드시 떠오를 것이다.

hdu2825 Wireless Password [ac 로봇 + dp 상태 압축]

그리고 4057은 dp수조가 3차원에서 2진법으로 표시될 뿐만 아니라 1차원에서도 스크롤 수조가 압축되어 있어 dp의 추측은 변하지 않았다. ATGC를 ABCD로 바꾸는 것은 넥스트 수조가 붙어 있기 때문이다@.그리고 주의는%2!!한 걸음 한 걸음!!그리고 점수의 계산, 반나절 동안 어떻게 점수를 누적할 것인가를 생각하고 예처리를 하려고 했습니다. dp이동은 반나절 동안 쓰지 못했는데 사실은 이진법 상태를 하나하나 들춰서 한 명씩 누적하면 됩니다. 그리고 struct의 용량은 가장 큰 요소인 *개에 따라 계산된 것 같습니다. 인터넷에서 이 문제를 말한 것 같아서 Kuangbin의 템플릿은 struct를 삭제하면 됩니다. 또queue의 존재로 인해next end 수조는 사용할 수 없습니다. 이름도 바꿔야 합니다. 그리고 수조가 경계를 넘으면 반드시 RE를 판정할 수 없습니다. WA일지도 모릅니다. 사실 이렇게 보면 이 유형 문제도 특별히 어렵지 않습니다.

/***********
hdu4057
2016.3.16
1450MS	9800K	3338B	C++
***********/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int score[110],dp[2][1005][1<<10];
int n,m,k;
int max(int a,int b){if(a>b)return a;return b;}
    int nxt[1005][4],fail[1005],nd[1010];
    int root,L;
    int newnode()
    {
        for(int i=0;i<4;i++)nxt[L][i]=-1;
        nd[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(char buf[],int id)
    {
        int len=strlen(buf);
        int now=root;
        for(int i=0;i<len;i++)
        {
            if(nxt[now][buf[i]-'A']==-1)
                nxt[now][buf[i]-'A']=newnode();
            now=nxt[now][buf[i]-'A'];
        }
        nd[now]|=(1<<id);
    }
    void build()
    {
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<4;i++)
            if(nxt[root][i]==-1)
                nxt[root][i]=root;
            else
            {
                fail[nxt[root][i]]=root;
                Q.push(nxt[root][i]);
            }
        while(!Q.empty())
        {
            int now=Q.front();
            Q.pop();
            nd[now]|=nd[fail[now]];
            for(int i=0;i<4;i++)
                if(nxt[now][i]==-1)
                    nxt[now][i]=nxt[fail[now]][i];
                else
                {
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    Q.push(nxt[now][i]);
                }
        }
    }
    void solve()
    {
       // printf("L=%d
",L);
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;///!!!
        for(int i=0;i<n;i++)
        {
            memset(dp[(i+1)%2],0,sizeof(dp[(i+1)%2]));
            for(int j=0;j<L;j++)
            {
                for(int k=0;k<(1<<m);k++)
                {
                    if(dp[i%2][j][k]==0)continue;//!!
                    for(int x=0;x<4;x++)
                    {
                        int newi=(i+1)%2;
                        int newj=nxt[j][x];//!!
                        int newk=k|nd[newj];
                        dp[newi][newj][newk]=dp[i%2][j][k];
                  //  printf("newi=%d newj=%d newk=%d dp=%d
",newi,newj,newk,dp[newi][newj][newk]);
                    }
                }
            }
        }
        int cnt=-0xfffffff;
        for(int j=0;j<L;j++)
        {
            for(int i=0;i<(1<<m);i++)
            {
                int ans=0;
                if(!dp[n%2][j][i])continue;
                for(int g=0;g<m;g++)
                {
                    if(i&(1<<g)) ans+=score[g];
                }
              //  printf("ans=%d
",ans);
                cnt=max(ans,cnt);
            }
        }
        if(cnt<0)printf("No Rabbit after 2012!
");
        else printf("%d
",cnt);
        return ;
    }

char buf[200];
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d",&m,&n))
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%s",buf);
            for(int i=0;i<strlen(buf);i++)
            {
                if(buf[i]=='G')buf[i]='B';
                if(buf[i]=='T')buf[i]='D';
            }
            scanf("%d",&score[i]);
            insert(buf,i);
        }
        build();
        solve();
    }
    return 0;
}