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.

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 a single integer, which is the minimum number of additional voters needed to ensure that no overall winner exists.

Sample Input 1 | Sample Output 1 |
---|---|

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