Problem D
Condorcet

Consider an election where there are some candidates, one winner, and each voter has a complete ranked preference of the candidates. One possible method of determining the winner is to examine each pair of candidates and see which would win in a head-to-head matchup (i.e., which candidate has more voters that rank them higher than their opponent) and then see if there is a single candidate that wins all their head-to-head matchups. This is called the Condorcet Method.

For simplicity, let ABC denote a vote that prefers A over B, and B over C. As an example, imagine that there are three votes: ABC, BAC, and CAB. Then A wins in a head-to-head matchup against B 2:1, and A also wins against C 2:1, so we could declare A the winner overall.

Note that a winner does not always exist; for example, imagine that the three votes were ABC, BCA, and CAB instead. Then A wins against B 2:1, B wins against C 2:1, and C wins against A 2:1. There is no single candidate that wins all their head-to-head matchups.

You are given the candidates and a set of votes. What is the minimum number of additional voters you would need to add (whose preferences you can individually control) in order to ensure that no overall winner exists? Assume that ties are broken by some tiebreaker you do not control and cannot predict. Therefore, you need to have every candidate lose a head-to-head matchup with some other candidate.

Input

The first line of input contains two integers, $n$ ($3 \le n \le 5$) and $m$ ($1 \le m \le n!$), where $n$ is the number of candidates, and $m$ is the number of vote tally lines. The candidates are represented by the first $n$ upper-case letters of the alphabet.

Each of the next $m$ lines contains a string $s$ and an integer $k$ ($1 \le k \le 10^6$). These are the vote tallies, which each consist of a string $s$ defining the vote, and an integer count $k$ indicating how many votes of type $s$ are represented by that tally line. The string $s$ describing a vote contains the first $n$ upper-case letters, each exactly once, in some order. The votes in the vote tally lines are unique.

Output

Output a single integer, which is the minimum number of additional voters needed to ensure that no overall winner exists.

3 6
ABC 1
ACB 2
BAC 3
BCA 4
CAB 5
CBA 6

6