OI题库

Problem 4

稗田阿求(akyuu.cpp/c/pas)

题目描述

在幻想乡，稗田乙女是负责书写《幻想乡缘起》的家族。由于需要代代相传关于幻想乡的记忆，稗田乙女采用了一些特殊的记录方式。对于相同重复的文字，稗田乙女会用一个数字来代替，然后用一个数列来表示一个段文字。比如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..2*M+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 ≤ 60

对于100%的数据：1 ≤ L ≤ 100

注意

保证每一组文字段和数列组合均合法；

在一组文字段和数列组合里面不会出现多个字符对一个数字，或是一个字符对多个数字的情况。