콩도르세

후보가 여럿이고 당선자가 한 명인 선거를 생각해 보자. 각 유권자는 후보 전체를 완전한 순위로 매긴 선호를 갖는다. 당선자를 정하는 한 방법은 후보를 두 명씩 짝지어 일대일 대결을 붙이는 것이다. 이 대결에서는 상대보다 자신을 더 높게 순위 매긴 유권자가 많은 후보가 이긴다. 그다음 모든 일대일 대결에서 이기는 후보가 단 한 명 있는지 확인한다. 이를 콩도르세 방법(Condorcet Method)이라고 한다.

간단히 하기 위해, ABC는 A를 B보다, B를 C보다 선호하는 표를 뜻한다. 예를 들어 표가 ABC, BAC, CAB 세 장이라고 하자. 그러면 A가 B를 2:1로 이기고, A가 C를 2:1로 이기므로 A를 전체 승자로 선언할 수 있다.

전체 승자가 항상 존재하는 것은 아니다. 예를 들어 표가 ABC, BCA, CAB라면 A가 B를 2:1로 이기고, B가 C를 2:1로 이기며, C가 A를 2:1로 이긴다. 모든 일대일 대결에서 이기는 후보는 한 명도 없다.

후보와 표 집합이 주어졌을 때, 전체 승자가 존재하지 않도록 하려면 최소 몇 명의 유권자를 추가해야 하는가? 추가하는 유권자의 선호는 각자 직접 정할 수 있다. 동점은 제어할 수 없고 예측할 수도 없는 규칙으로 깬다고 가정한다. 따라서 모든 후보가 다른 어떤 후보와의 일대일 대결에서 반드시 져야 한다.

첫째 줄에 두 정수 $n$ ($3 \le n \le 5$)과 $m$ ($1 \le m \le n!$)이 주어진다. 여기서 $n$은 후보의 수이고, $m$은 득표 집계 줄의 수이다. 후보는 알파벳 대문자 앞 $n$개로 나타낸다.

다음 $m$개 줄에는 문자열 $s$와 정수 $k$ ($1 \le k \le 10^6$)가 주어진다. 각 줄은 투표 유형 $s$와 그 유형의 표가 $k$표임을 뜻한다. 문자열 $s$는 대문자 앞 $n$개를 각각 정확히 한 번씩, 어떤 순서로든 포함한다. 집계 줄에 있는 표는 모두 서로 다르다.

전체 승자가 존재하지 않도록 하는 데 필요한 추가 유권자의 최소 수를 정수 하나로 출력한다.