#1950. 匹配项

匹配项

题目描述

定义“匹配项”是一个长度为 LL 的字符串,每一位要么是 0,要么是 1。现在有 NN 个这样的“匹配项”,我们希望设计一个“方案”,“方案”同样是长度为LL的字符串,每一位要么是 0,要么是 1。定义每个“匹配项”的错误值为“方案”与“匹配项”不同位的个数,比如“匹配项”是 101,“方案”是 000,那么两者的第一位和第三位是不同的,所以该“方案”对于该“匹配项”的错误值为 2。我们希望找到一个“方案”,使得这 NN 个“匹配项”的错误值之和最小。此外,有 MM 个互不相同的禁用“方案”,我们要求找到的“方案”不能是禁用“方案”之一。

输入格式

输入的第一行包含三个正整数 N,M,LN,M,L

接下来输入 NN 行,每行为一个长度为 LL 的字符串,之后 MM 行,每行为一个长度为 LL 的字符串。

输出格式

输出一个整数,表示满足要求的“方案”得到的这NN个“匹配项”的最小错误值之和。

样例 #1

样例输入 #1

4 1 4
0000
1000
1100
1010
1000

样例输出 #1

5

样例 #2

样例输入 #2

2 4 4
0000
0000
0000
1000
0100
0010

样例输出 #2

2

提示

保证 1N10001 \le N \le 1000, 1Mmin(1000,2L1)1 \le M \le \min(1000,2^L-1) , 1L1000 1 \le L \le 1000