#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;
            }
        }
    }

    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});
        }

        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;
                    }
                    return;
                }
            }
            vis[node] = 2;
        };

        bool valid = 1;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                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() && (g2 == -1e9 || abs(g2) < g1))) {
                    valid = 0;
                    break;
                }
            }
        }

        if (!valid){
            break;
        }

        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;
}