考虑一场选举，其中有若干候选人，产生一名获胜者，且每位选民对候选人都有完整的排名偏好。确定获胜者的一种可能方法是检查每一对候选人，看谁能在两两对决中获胜（即哪位候选人获得的选票中，将其排在对手之前的选民更多），然后查看是否存在一位候选人在其所有两两对决中均获胜。这被称为孔多塞准则（Condorcet Method）。

为简便起见，令 $ABC$ 表示一种偏好 A 优于 B，且 B 优于 C 的选票。例如，假设有三张选票：$ABC$、$BAC$ 和 $CAB$。那么在 A 与 B 的对决中，A 以 2:1 获胜；在 A 与 C 的对决中，A 也以 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$ 个大写字母，每个字母恰好出现一次，顺序不限。选票统计行中的选票类型是唯一的。

输出格式

输出一个整数，即为确保不存在总获胜者所需添加的最少额外选民数量。

样例

输入 1

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

输出 1

6