#include <bits/stdc++.h>
using namespace std;
//
const int mnum = 1e5 + 5;
const int maxn = 3e5 + 5;
//
int n, m, p[maxn];
string s[maxn];
//
namespace Trie
{
    struct Node
    {
        int cnt;
        long long val;
        Node *par, *child[26];
        //
        Node (void) : cnt(0), val(0)
        {
            fill(child, child + 26, nullptr);
        }
    };
    //
    Node *root = new Node();
    Node *en[maxn];
    //
    void insert (int id)
    {
        int c;
        Node *p = root;
        //
        for (char f : s[id])
        {
            c = f - 'A';
            if (p->child[c] == nullptr)
                p->child[c] = new Node(),
                p->child[c]->par = p;
            p = p->child[c];
            ++p->cnt;
        }
        en[id] = p;
    }
    void erase (int id, long long v)
    {
        Node *temp, *p = en[id];
        //
        while (p != root)
        {
            temp = p->par;
            if (--p->cnt == 0)
                delete(p);
            p = temp;
            p->val = max(p->val, v);
        }
    }
}
//
int check_sub (void)
{
    int mx = 0;
    //
    for (int i = 1; i <= n; ++i)
        mx = max(mx, (int)s[i].length());
    if (n <= 100 && mx <= 100 && m <= 100)
        return 1;
    if (m == 0)
        return 2;
    return 3;
}
namespace subtask_1
{
    vector<int> lucky[mnum];
    long long dp[maxn];
    //
    void solve (void)
    {
        for (int u, v; m--;)
            cin >> u >> v,
            lucky[u].emplace_back(v),
            lucky[v].emplace_back(u);

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j < i; ++j)
                if (s[j].size() > s[i].size() && s[j].substr(0, s[i].size()) == s[i])
                    dp[i] = max(dp[i], dp[j]);
            for (int x : lucky[p[i]])
                for (int j = 1; j < i; ++j)
                    if (p[j] == x)
                        dp[i] = max(dp[i], dp[j]);
            dp[i] += p[i];
        }

        cout << *max_element(dp + 1, dp + n + 1);
    }
}
namespace subtask_2
{
    void solve (void)
    {
        long long temp, ans = 0;
        //
        for (int i = 1; i <= n; ++i)
            Trie::insert(i);
        for (int i = 1; i <= n; ++i)
            temp = Trie::en[i]->val + p[i],
            ans = max(ans, temp),
            Trie::erase(i, temp);
        cout << ans;
    }
}
namespace subtask_3
{
    const int orz = 500;
    //
    vector<int> lucky[mnum];
    vector<int> heavy[mnum];
    long long num[mnum], lazy[mnum];
    //
    void build (void)
    {
        for (int u = 1; u < mnum; ++u)
            for (int v : lucky[u])
                if (lucky[v].size() > orz)
                    heavy[u].emplace_back(v);
    }
    void update (int u, long long val)
    {
        lazy[u] = val;
        if (lucky[u].size() <= orz)
            for (int v : lucky[u])
                num[v] = max(num[v], lazy[u]);
    }
    long long get (int u)
    {
        long long res = num[u];
        //
        for (int v : heavy[u])
            res = max(res, lazy[v]);
        return res;
    }
    //
    void solve (void)
    {
        long long temp, ans = 0;
        //
        for (int u, v; m--;)
            cin >> u >> v,
            lucky[u].emplace_back(v),
            lucky[v].emplace_back(u);

        build();
        for (int i = 1; i <= n; ++i)
            Trie::insert(i);
        for (int i = 1; i <= n; ++i)
        {
            temp = max(Trie::en[i]->val, get(p[i])) + p[i];
            ans = max(ans, temp);
            Trie::erase(i, temp);
            update(p[i], temp);
        }

        cout << ans;
    }
}
//
void process (void)
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> s[i] >> p[i];
    //
    int sub = check_sub();
    //
    if (sub == 1)
        return subtask_1::solve();
    if (sub == 2)
        return subtask_2::solve();
    subtask_3::solve();
}
//
signed main (void)
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    process();
}