import itertools
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[0]*N for _ in range(N)]
for _ in range(M):
  s,k=input().split();k=int(k)
  for i in range(N):
    for j in range(i+1,N):
      G[ord(s[i])-65][ord(s[j])-65]+=k
      G[ord(s[j])-65][ord(s[i])-65]-=k

ans=1e9
for r in range(3,N+1):
  for nCr in itertools.combinations(range(N),r):
    for perm in itertools.permutations(range(1,r)):
      A=[nCr[0]]
      for i in perm:A.append(nCr[i])
      B=[0]*r
      for i in range(r):B[i]=G[A[i-1]][A[i]]
      s=sum(B)
      t=0
      if s<0:t=(r-s-1)//(r-1)+1
      t=max(t,1-min(B))
      ans=min(ans,t)
print(ans)