// Arup Guha
// 4/3/2021
// Solution to 2020 SER Problem D: Condorcet

import java.util.*;

public class condorcet_hp {

	public static int n;
	public static int factn;
	public static int[] votes;
	public static int maxVotes;
	public static int[][] headToHead;

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		factn = fact(n);
		int k = stdin.nextInt();
		votes = new int[factn];
		headToHead = new int[n][n];
		maxVotes = 0;
		
		// Update all the votes.
		for (int i=0; i<k; i++) {
			int idx = convert(stdin.next());
			votes[idx] += stdin.nextInt();
			maxVotes = Math.max(maxVotes, votes[idx]);
		}
		
		// Set up head to head array.
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {		
				for (int z=0; z<votes.length; z++) {
					if (beat(z, i, j))
						headToHead[i][j] += votes[z];
					else
						headToHead[j][i] += votes[z];
				}
			}
		}

		// Solve it!
		if (zero())
			System.out.println(0);
		else 
			System.out.println(go(new int[n], 0));
	}
	
	// Returns true if the answer is 0.
	public static boolean zero() {
	
		// Try each person as the winner.
		for (int i=0; i<n; i++) {
		
			// See how many contests person i wins or ties.
			int winOrTie = 0;
			for (int j=0; j<n; j++) {
				if (i == j) continue;
				if (headToHead[i][j] >= headToHead[j][i]) winOrTie++;
			}
		
			// We have a non-loser.
			if (winOrTie == n-1) return false;
		}
		
		// If we get here, no one won!
		return true;
	}
	
	// Set up equations - perm[i] is who beats i. So i gets strictly less votes than perm[i].
	public static int eval(int[] perm) {
		
		// Our variables are # of each type of the n! votes.
		Simplex myS = new Simplex(factn);
		
		// Go through each equation for who beats person i.
		for (int i=0; i<n; i++) {
			
			// This is the equation for person i.
			double[] eqn = new double[factn];
			
			// How much perm[i] is currently beating i by, minus 1.
			int diff = headToHead[perm[i]][i] - headToHead[i][perm[i]] - 1;
			
			// My votes get added, yours subtracted.
			int RHS = 0;
			for (int j=0; j<fact(n); j++) {
				if (beat(j, i, perm[i])) 	eqn[j] = 1;
				else 						eqn[j] = -1;
			}
			
			// Mine minus yours must be <= diff. (Otherwise you,perm[i], don't beat me...)
			myS.addUpperBound(eqn, diff);
		}
		
		// Flip the objective function. We are maximizing -(# of added votes).
		double[] obj = new double[factn];
		Arrays.fill(obj, -1);
		myS.setObjective(obj);
		
		// Solve and return.
		double tmpRes = myS.getMaximum();
		int added = (int)(tmpRes);
		
		// This is the corresponding # of votes actually added.
		return -added;
	}
	
	// Returns the best solution where the first k items of perm are fixed.
	// perm[i] is who beats person i...
	public static int go(int[] perm, int k) {
	
		// Got an arrangement, try it.
		if (k == n) {
			if (inconsistent(perm)) return 1000000000;
			return eval(perm);
		}
		
		int res = 1000000000;
		
		// Try each item in slot k, except k itself.
		for (int i=0; i<n; i++) {
			if (k == i) continue;
			perm[k] = i;
			res = Math.min(res, go(perm, k+1));
		}
		
		// Ta da!
		return res;
	}
	
	// Returns true iff this setting is inconsistent.
	public static boolean inconsistent(int[] perm) {
		
		// Look at each entry.
		for (int i=0; i<n; i++) {
			int other = perm[i];
			
			// A beats B AND B beats A is impossible.
			if (perm[other] == i) return true;
		}
		return false;
	}
	
	// Returns n!
	public static int fact(int n) {
		int res = 1;
		for (int i=1; i<=n; i++) res *= i;
		return res;
	}
	
	// Converts s to its lexicographical rank value, 0-based.
	public static int convert(String s) {
	
		int res = 0;
		boolean[] used = new boolean[n];
		
		// Go through each item.
		for (int i=0; i<n; i++) {
			
			int cur = s.charAt(i) - 'A';
			int mult = 0;
			
			// See how many valid items we are skipping over.
			for (int j=0; j<cur; j++) 
				if (!used[j])
					mult++;
					
			// This is what we add to our rank.
			res += mult*fact(n-1-i);
			used[cur] = true;
		}
		return res;
	}
	
	// For variable idx, returns the corresponding vote permutation.
	public static int[] cBack(int idx) {
	
		boolean[] used = new boolean[n];
		int[] res = new int[n];
		
		// Go through each slot.
		for (int i=0; i<n; i++) {
			
			// Current rank from items left we must put in this slot.
			int rank = idx/fact(n-1-i);
			
			int cnt = 0;
			
			// Find the rank based letter of those unused.
			for (int j=0; j<n; j++) {
				if (!used[j]) cnt++;
				if (cnt == rank+1) {
					used[j] = true;
					res[i] = j;
					break;
				}
			}
			
			// Subtract the effect of this item from idx.
			idx -= (fact(n-1-i)*rank);
		}
		
		return res;
	}
	
	// Returns true iff a beats b in vote number idx.
	public static boolean beat(int idx, int a, int b) {
		
		// Get the permutation.
		int[] perm = cBack(idx);
		
		// See if a comes first or not.
		for (int i=0; i<n; i++) {
			if (perm[i] == a) return true;
			if (perm[i] == b) return false;
		}
		
		// Dummy statement for Java.
		return true;
	}
	
}

/*** UCF Hackpack Code for Simplex Below ***/

class Simplex {
	static double eps = 1e-9, oo = 1e16, max;
	int m, n;
	int[] B, N;
	double[][] mat;
	ArrayList<Double> vals;
	ArrayList<double[]> eqs;
	double[] obj, solution;

	public Simplex(int n) {
		this.n = n;
		obj = new double[n];
		Arrays.fill(obj, 1.0);
		eqs = new ArrayList<>();
		vals = new ArrayList<>();
	}

	public void setObjective(double[] obj) {
		this.obj = obj;  clearSolution();
	}

	public void addUpperBound(double[] equation, double value) {
		double[] eq = new double[equation.length];
		for (int i = 0; i < equation.length; i++)
			eq[i] = equation[i];
		eqs.add(eq);
		vals.add(value);
	}

	public void addLowerBound(double[] equation, double value) {
		double[] eq = new double[equation.length];
		for (int i = 0; i < equation.length; i++)
			eq[i] = -equation[i];
		eqs.add(eq);
		vals.add(-value);
	}

	//#
	public void addEquality(double[] equation, double value) {
		addLowerBound(equation, value);
		addUpperBound(equation, value);
	}

	public void addUpperBound(int idx, double value) {
		double[] eq = new double[n];
		eq[idx] = 1;
		addUpperBound(eq, value);
	}

	public void addLowerBound(int idx, double value) {
		double[] eq = new double[n];
		eq[idx] = 1;
		addLowerBound(eq, value);
	}

	public void addEquality(int idx, double value) {
		double[] eq = new double[n];
		eq[idx] = 1;
		addEquality(eq, value);
	}
	//$

	void clearSolution() { solution = null; }

	double[] getSolution() {
		if (solution == null)  solve();
		return solution;
	}

	double getMaximum() {
		if (solution == null)  solve();
		return max;
	}

	private void buildMatrix() {
		m = eqs.size();
		N = new int[n + 1];
		B = new int[m];
		mat = new double[m + 2][n + 2];
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				mat[i][j] = eqs.get(i)[j];
		for (int i = 0; i < m; i++) {
			B[i] = n + i;
			mat[i][n] = -1;
			mat[i][n + 1] = vals.get(i);
		}
		for (int j = 0; j < n; j++)
			mat[m][j] = -obj[N[j] = j];
		mat[m + 1][n] = -(N[n] = -1);
	}

	private void pivot(int r, int s) {
		for (int i = 0; i < m + 2; i++)
			if (i != r)
				for (int j = 0; j < n + 2; j++)
					if (j != s)
						mat[i][j] -= mat[r][j] * mat[i][s] / mat[r][s];
		for (int j = 0; j < n + 2; j++)
			if (j != s)
				mat[r][j] /= mat[r][s];
		for (int i = 0; i < m + 2; i++)
			if (i != r)
				mat[i][s] /= -mat[r][s];
		mat[r][s] = 1.0 / mat[r][s];
		B[r] = B[r] ^ N[s] ^ (N[s] = B[r]);
	}

	private boolean runSimplex(int phase) {
		int x = phase == 1 ? m + 1 : m;
		while (true) {
			int s = -1;
			for (int j = 0; j <= n; j++)
				if ((phase != 2 || N[j] != -1)
						&& (s == -1 || mat[x][j] < mat[x][s] || mat[x][j] == mat[x][s] && N[j] < N[s]))
					s = j;
			if (mat[x][s] >= -eps)
				return true;
			int r = -1;
			for (int i = 0; i < m; i++) {
				if (mat[i][s] < eps)
					continue;
				if (r == -1 || mat[i][n + 1] / mat[i][s] < mat[r][n + 1] / mat[r][s]
						|| mat[i][n + 1] / mat[i][s] == mat[r][n + 1] / mat[r][s] && B[i] < B[r])
					r = i;
			}
			if (r == -1)
				return false;
			pivot(r, s);
		}
	}

	private double solve() {
		buildMatrix();
		int r = 0;
		for (int i = 1; i < m; i++)
			if (mat[i][n + 1] < mat[r][n + 1])
				r = i;
		if (mat[r][n + 1] <= -eps) {
			pivot(r, n);
			if (!runSimplex(1) || mat[m + 1][n + 1] < -eps)
				return max = -oo;
			for (int i = 0; i < m; i++)
				if (B[i] == -1) {
					int s = -1;
					for (int j = 0; j <= n; j++)
						if (s == -1 || mat[i][j] < mat[i][s] || mat[i][j] == mat[i][s] && N[j] < N[s])
							s = j;
					pivot(i, s);
				}
		}
		solution = new double[n];
		if (!runSimplex(2))
			return max = oo;
		solution = new double[n];
		for (int i = 0; i < m; i++)
			if (B[i] < n)
				solution[B[i]] = mat[i][n + 1];
		return max = mat[m][n + 1];
	}
}