#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;#define mod 2100000000#define pb push_back#define lowbit(x) ((x)&(-x))struct node{ int son[4],fail; int cnt; node(){memset(son,0,sizeof(son));fail=0;cnt=0;}};vector<node> ac;int hash[256];bool dp[101][1<<10][210];int n,m,cost[11];int map[1<<10];void init() { memset(map,0,sizeof(map)); for(int i=0;i<m;++i) map[1<<i]=cost[i]; for(int i=0;i<(1<<m);++i) { map[i]=map[i^lowbit(i)]+map[lowbit(i)]; }}void insert(const char *str,int num) { int p=0,i=0; while(str[p]) { if(!ac[i].son[hash[str[p]]]) { ac[i].son[hash[str[p]]]=ac.size(); ac.pb(node()); } i=ac[i].son[hash[str[p]]]; ++p; } ac[i].cnt=1<<num;}void getFail() { queue<int> qu; qu.push(0); while(!qu.empty()) { int cur=qu.front();qu.pop(); for(int i=0;i<4;++i) { int nex=ac[cur].son[i]; int p=ac[cur].fail; if(nex) { qu.push(nex); if(~p) ac[nex].fail=ac[p].son[i],ac[nex].cnt|=ac[ac[p].son[i]].cnt; else ac[nex].fail=0; } else { if(~p) ac[cur].son[i]=ac[p].son[i]; } } }}int main() { ios::sync_with_stdio(false); hash['A']=0; hash['T']=1; hash['C']=2; hash['G']=3; while(cin >> m >> n) { ac.clear(); ac.pb(node()); ac[0].fail=-1; for(int i=0;i<m;++i) { char str[102]; cin >> str >> cost[i]; insert(str,i); } init(); getFail(); for(int i=0;i<=n;++i) for(int j=0;j<(1<<m);++j) for(int k=0;k<ac.size();++k) dp[i][j][k]=false; dp[0][0][0]=true; int ans=-1; for(int i=0;i<n;++i) for(int j=0;j<(1<<m);++j) for(int k=0;k<ac.size();++k) { if(!dp[i][j][k]) continue; for(int p=0;p<4;++p) { int spos=ac[k].son[p],sta=j|ac[spos].cnt; dp[i+1][sta][spos]=true; } } for(int i=0;i<(1<<m);++i) for(int j=0;j<ac.size();++j) if(dp[n][i][j]&&map[i]>ans) { ans=map[i]; } if(~ans) cout << ans << endl; else cout << "No Rabbit after 2012!" << endl; } return 0;}
