#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

#define D(x) 

const int MAX_N = ;

const int MAX_LEN = ;

const int MAX_CHILD_NUM = ;

const int MAX_NODE_NUM = MAX_LEN * MAX_N;

//1.init() 2.insert() 3.build() 4.query()

struct Trie

{

    int next[MAX_NODE_NUM][MAX_CHILD_NUM];

    int fail[MAX_NODE_NUM];

    int count[MAX_NODE_NUM];

    int node_cnt;

    bool vis[MAX_NODE_NUM]; //set it to false

    int root;

    void init()

    {

        node_cnt = ;

        root = newnode();

        memset(vis, , sizeof(vis));

    }

    int newnode()

    {

        for (int i = ; i < MAX_CHILD_NUM; i++)

            next[node_cnt][i] = -;

        count[node_cnt++] = ;

        return node_cnt - ;

    }

    int get_id(char a)

    {

        if (a == 'A')

            return ;

        if (a == 'T')

            return ;

        if (a == 'C')

            return ;

        return ;

    }

    void insert(char buf[], int id)

    {

        int now = root;

        for (int i = ; buf[i]; i++)

        {

            int id = get_id(buf[i]);

            if (next[now][id] == -)

                next[now][id] = newnode();

            now = next[now][id];

        }

        count[now] |= ( << id);

    }

    void build()

    {

        queue<int>Q;

        fail[root] = root;

        for (int i = ; i < MAX_CHILD_NUM; i++)

            if (next[root][i] == -)

                next[root][i] = root;

            else

            {

                fail[next[root][i]] = root;

                Q.push(next[root][i]);

            }

        while (!Q.empty())

        {

            int now = Q.front();

            Q.pop();

            for (int i = ; i < MAX_CHILD_NUM; i++)

                if (next[now][i] == -)

                    next[now][i] = next[fail[now]][i];

                else

                {

                    fail[next[now][i]]=next[fail[now]][i];

                    count[next[now][i]] |= count[fail[next[now][i]]];

                    Q.push(next[now][i]);

                }

        }

    }

    int query(char buf[])

    {

        int now = root;

        int res = ;

        memset(vis, , sizeof(vis));

        for (int i = ; buf[i]; i++)

        {

            now = next[now][get_id(buf[i])];

            int temp = now;

            while (temp != root && !vis[temp])

            {

                res += count[temp];

                 // optimization: prevent from searching this fail chain again.

                //also prevent matching again.

                vis[temp] = true;

                temp = fail[temp];

            }

        }

        return res;

    }

    void debug()

    {

        for(int i = ;i < node_cnt;i++)

        {

            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],count[i]);

            for(int j = ;j < MAX_CHILD_NUM;j++)

                printf("%2d",next[i][j]);

            printf("]\n");

        }

    }

}ac;

const int MAX_STATUS = ( << ) + ;

int n, len;

char st[MAX_LEN];

int w[MAX_N];

bool dp[][MAX_NODE_NUM][MAX_STATUS];

int cal(int status)

{

    int ret = ;

    for (int i = ; i < n; i++)

    {

        if (status & ( << i))

            ret += w[i];

    }

    return ret;

}

int work()

{

    int ret = -;

    memset(dp, , sizeof(dp));

    dp[][ac.root][] = true;

    for (int i = ; i < len; i++)

    {

        for (int j = ; j < ac.node_cnt; j++)

            for (int status = ; status < ( << n); status++)

                dp[(i + ) & ][j][status] = false;

        D(printf("%d\n", dp[(i + ) & ][][]));

        for (int j = ; j < ac.node_cnt; j++)

        {

            for (int status = ; status < ( << n); status++)

            {

                if (!dp[i & ][j][status])

                    continue;

                for (int k = ; k < ; k++)

                {

                    int v = ac.next[j][k];

                    dp[(i + ) & ][v][status | ac.count[v]] = true;

                    D(printf("%d %d\n", j, status));

                    D(printf("%d %d %d %d\n", (i + ) & , v, status | ac.count[v], dp[(i + ) & ][][]));

                }

            }

        }

    }

    for (int i = ; i < ac.node_cnt; i++)

        for (int status = ; status < ( << n); status++)

        {

            if (dp[len & ][i][status])

            {

                if (dp[len & ][i][] && status == )

                {

                    D(printf("*%d %d\n", i, ac.count[i]));

                }

                ret = max(ret, cal(status));

            }

        }

    return ret;

}

int main()

{

    while (scanf("%d%d", &n, &len) != EOF)

    {

        ac.init();

        for (int i = ; i < n; i++)

        {

            scanf("%s%d", st, &w[i]);

            ac.insert(st, i);

        }

        ac.build();

        int ans = work();

        if (ans < )

            puts("No Rabbit after 2012!");

        else

            printf("%d\n", ans);

    }

    return ;

}