#include<bits/stdc++.h>

#define int long long
#define endl '\n'
using namespace std;

void doWork() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> mat(n, vector<int>(n));
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        int vv;
        cin >> vv;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                mat[s[j] - 'A'][s[k] - 'A'] += vv;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            if (mat[i][j] >= mat[j][i]) {
               // cout << i << " " << j << " " << mat[i][j] - mat[j][i] + 1 << endl;
            }

        }
    }

    vector<vector<int>> all;
    function<void(int, vector<int>)> rec = [&](int i, vector<int> cur) -> void {
        if (i == n) {
            all.push_back(cur);
            return;
        }

        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            cur.push_back(j);
            rec(i + 1, cur);
            cur.pop_back();
        }
    };

    rec(0, {});
    int ans = 1e9;
    for (auto &v: all) {
        vector<vector<pair<int, int>>> adj(n);
        int mx = 0;

        for (int A = 0; A < n; A++) {
            int B = v[A];
            int w = mat[A][B] - mat[B][A] + 1;
            mx = max(mx, w);
            adj[B].push_back({A, w});
          //  cout << B << " " << A << " " << w << endl;

        }
       // cout << endl;
        vector<int> vis(n);
        vector<pair<int, int>> p(n);
        vector<int> cyc;

        function<void(int)> dfs = [&](int node) -> void {
            vis[node] = 1;
            for (auto[to, w]: adj[node]) {
                if (!vis[to])
                    p[to].first = node, p[to].second = w, dfs(to);
                else if (vis[to] == 1) {
                    int cur = node, ww = w;
                    while (cur != p[to].first) {
                        cyc.push_back(ww);
                        ww = p[cur].second;
                        cur = p[cur].first;
                    }
                    cyc.push_back(ww);
                    return;
                }
            }
            vis[node] = 2;
        };

        bool valid = 1;
        for (int i = 0; i < n; i++) {
            if ( vis[i])
                continue;
            cyc.clear();
            dfs(i);
            std::sort(cyc.begin(), cyc.end());
            int g2 = -1e9, g1 = 0;
            for (int j: cyc) {

                if (j <= 0)
                    g2 = j;
                else {
                    g1 = j;
                }
            }
            if ((cyc.size() &&  abs(g2) < g1)) {
               mx = max( mx , mx + (g1 - abs(g2)));
            }
            if (cyc.size() && g2 == -1e9) {
                mx = max( mx , mx *2  + cyc[0]);
            }
        }

        if (valid) {

            ans = min(ans, mx);
        }
    }
    cout << ans << '\n';
}


signed main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
//    freopen("bisector.in","r",stdin);
//    freopen("bisector.out","w",stdout);
    int t = 1;
    // cout << primes.size() << endl;
//    cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}