#P2724. Purifying Machine

Purifying Machine

描述

Mike 是一家奶酪厂的老板,他有 2N2N 块奶酪,每块奶酪都被分配了一个二进制编号,从 00000\ldots011111\ldots1。为了保证奶酪不被病毒感染,他制造了一台净化机来清理被病毒感染的奶酪。这台净化机设计得很特殊:它有 NN 个开关,每个开关有三种状态,分别为 1100*
一次操作就是根据这 NN 个开关的状态进行一次清理动作。在一次操作中,最多只能有一个开关处于 * 状态,该状态可以代替 1100。当净化机被调到某一特定状态时,将会清理与该二进制状态对应的所有奶酪。
例如,如果 N=6N=6,开关状态为 0110001*100,则该操作会清理编号为 010100010100011100011100 的奶酪。

一天,Mike 的机器被感染了。当 Mike 发现时,他已经对奶酪进行了一些操作,结果操作过的奶酪也都被感染。Mike 迅速清理了机器,但现在他需要用最少的操作次数清理掉所有受感染的奶酪。
清理时要求:

  • 如果一块奶酪是被感染的,那么用机器对该奶酪操作一次或多次就能使其复原;
  • 如果奶酪没有被感染,操作它会使奶酪变坏。

给定 Mike 已经做过的感染操作,求必须再进行的最少操作次数,使得所有被感染的奶酪都能清理,而不会使未感染的奶酪变坏。

输入

输入包含若干测试用例。
每个测试用例的第一行包含两个整数 NNMM,其中 1N101 \le N \le 10 表示开关数量,1M10001 \le M \le 1000 表示 Mike 已经做过的感染操作次数。
接下来的 MM 行,每行给出一个长度为 NN 的字符串,表示一次感染操作时机器的开关状态。
测试用例以一行 "0 00\ 0" 结束,不处理此测试用例。

输出

对于每个测试用例,输出一行一个整数,表示 Mike 还需要进行的最少操作次数。

3 3
*01
100
011
0 0
2

题目来源

Beijing 2005