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

/*** Note: In contest this would get a TLE. I wanted to reformulate the            
           equations so that the 0 vector was a satisfiable solution and
		   that we were maximizing an objective function instead of minimizing.
		   The strategy is to give everyone equal votes and then add extra 
		   votes to ensure that the appropriate people win head to heads.
		   Then, try to maximize the votes you take away from this feasible
		   solution to get another one that is feasible. This was practice to
		   make sure I understood reformulating equations into equivalent ones.
***/

import java.util.*;

public class condorcet_hp_alt {

	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.
		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];
				}
			}
		}
		
		//print(headToHead);
		
		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) {
		
		// Gets a set of votes that satisfies these constraints.
		int[] satisfy = getValid(perm);
		
		// How many votes we added to get this satisfiable solution.
		int added = 0;
		for (int i=0; i<factn; i++)
			added += (satisfy[i] - votes[i]);
	
		// # of variables and equations for Simplex.
		Simplex myS = new Simplex(factn);
		
		// Go through each equation for who beats person i.
		for (int i=0; i<n; i++) {
			
			double[] eqn = new double[factn];
			
			// Yours get added, mine subtracted, since the x's are "negative" votes.
			int RHS = 0;
			for (int j=0; j<fact(n); j++) {
				if (beat(j, i, perm[i])) {
					eqn[j] = -1;
					RHS -= satisfy[j];
				}
				else {
					eqn[j] = 1;
					RHS += satisfy[j];
				}
			}
			
			// This shows that you can't take away more votes from me than you
			// adjusted by the values in satisfy.
			myS.addUpperBound(eqn, RHS-1);
		}
		
		// Limit on each variable (votes we take away).
		for (int i=0; i<factn; i++) {
			double[] eqn = new double[factn];
			eqn[i] = 1;
			myS.addUpperBound(eqn,satisfy[i] - votes[i]);
			myS.addLowerBound(eqn, 0);
		}
		
		// Regular objective function.
		double[] obj = new double[factn];
		Arrays.fill(obj, 1);
		myS.setObjective(obj);
		
		// Solve and return.
		double tmpRes = myS.getMaximum();
		int remove = (int)(tmpRes);
		
		// This is the corresponding # of votes actually added.
		return added - remove;
	}
	
	// Returns a valid set of votes that satisfy this permutation.
	public static int[] getValid(int[] perm) {
		
		// This way no one loses votes.
		int[] res = new int[factn];
		Arrays.fill(res, maxVotes);
		
		// Go through each constraint.
		for (int i=0; i<n; i++) {
			
			int beatI = perm[i];
			
			// Go through each variable.
			for (int j=0; j<factn; j++) {
				
				if (beat(j, beatI, i))
					res[j]++;
			}
		}
		
		return res;
	}
	
	// Returns the best answer with first k items of perm fixed.
	// perm[i] is who beats 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) {
		
		int[] perm = cBack(idx);
		
		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 Hack Pack 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];
	}
}