题目描述

在幻想乡，稗田乙女是负责书写《幻想乡缘起》的家族。由于需要代代相传关于幻想乡的记忆，稗田乙女采用了一些特殊的记录方式。对于相同重复的文字，稗田乙女会用一个数字来代替，然后用一个数列来表示一个段文字。比如 $1$代表“$A$”，$2$代表“$C$”，那么$\{1,2\}$就代表“$AC$”，$\{2,1,2\}$就代表“$CAC$”。不过由于年代过于久远，到阿求时已经是第九代稗田乙女，所以难免会出现错误。现在阿求有$N$个数字$(1..N)$和$N$个字符(“$A$”..第$N$个字母)，以及一些以前传承下来的M组文字段和对应的数列。每一组文字段和数列相互对应，文字的第$i$个字符对应着数列的第$i$项。阿求想要知道怎样安排$N$ 个数字和字符的对应关系，能够使组数尽可能多的文字段和数列组合满足该对应关系。数字和字符间一一对应，不会出现多对一或一对多的情况。

输入

第1行：$2$个正整数$N, M$。 第$2..2M+1$行：每$2$行为一组，第$1$行为文字段落，第$2$行为数列。保证文字段落的字符数$L$等于数列数字个数$L$，且均在$1..N$。文字段落只包含大写字母。

输出

第1行：最多能够匹配的文字段落和数列组合数量。

输入样例

3 3 
ACCA 
1 3 3 1   
AAC 
2 2 1 
BCBC 
3 1 3 1

输出样例

2

提示

【样例解释】 当$A=2,B=3,C=1$时第$2、3$字符串和数列组合满足对应关系。 【数据规模】 对于60%的数据：$1≤N≤10，1≤M≤20$。 对于100%的数据：$1≤N≤26，1≤M≤40，1≤L≤100$。 【注意事项】 保证每一组文字段和数列组合均合法，在一组文字段和数列组合里面不会出现多个字符对一个数字，或是一个字符对多个数字的情况。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共10个测试点，非原站或官方原始数据。总分100分。