CF543C Remembering Strings

你有一个包含 $n$ 个长度相同的小写英文字母字符串的多重集合。如果对于集合中的每一个字符串，存在某个位置 $i$ 和某个英文字母 $c$，使得只有这一字符串在位置 $i$ 上是字母 $c$，我们就称这个集合为“容易记住”的。 例如，多重集合 {"abc", "aba", "adc", "ada"} 不是容易记住的。而集合 {"abc", "ada", "ssa"} 是容易记住的，因为： - 第一个字符串在第 $3$ 个位置上唯一出现了字符 $c$； - 第二个字符串在第 $2$ 个位置上唯一出现了字符 $d$； - 第三个字符串在第 $2$ 个位置上唯一出现了字符 $s$。 你想对多重集合做一些修改，使它变得容易记住。对于 $a_{ij}$ 个金币，你可以将第 $i$ 个字符串的第 $j$ 个位置上的字符改成任意其他小写字母。请计算最少需要多少金币，才能将该多重集合变成容易记住的。

第一行包含两个整数 $n$、$m$（$1 \leq n,m \leq 20$），分别表示集合中字符串的数量和每个字符串的长度。接下来的 $n$ 行，每行包含一个仅由小写英文字母组成的长度为 $m$ 的字符串。 接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行为 $a_{i1},a_{i2},...,a_{im}$（$0 \leq a_{ij} \leq 10^{6}$）。

输出一个整数，表示将集合变成容易记住所需支付金币的最小总和。

由 ChatGPT 5 翻译