您有 n 个长度相同的字符串的多组,由小写英文字母组成。我们会说,如果每个字符串都有英文字母表中的某个位置 i 和某个字母 c,则这些字符串很容易记住,这样该字符串是多重集中唯一在位置 i 具有字母 c 的字符串。
例如,字符串的多重集 {"abc", "aba", "adc", "ada"} 不容易记住。多重集 {"abc", "ada", "ssa"} 很容易记住,因为:
- 第一个字符串是唯一在位置 3 具有字符 c 的字符串;
- 第二个字符串是唯一在位置 2 具有字符 d 的字符串;
- 第三个字符串是唯一在位置 2 具有字符 s 的字符串。
您想要稍微更改一下多重集,以便于记住。对于 aij 硬币,您可以将第 i 个字符串的第 j 个位置的字符更改为英文字母表中的任何其他小写字母。找出您应该支付的最小金额是多少,以便使多组字符串易于记住。
输入
第一行包含两个整数 n, m (1 ≤ n, m ≤ 20) - 分别是多重集中的字符串数量和字符串长度。接下来的n行包含多重集的字符串,仅由小写英文字母组成,每个字符串的长度为m。
接下来 n 行每行包含 m 个整数,其中第 i 行包含整数 ai1、ai2、...、aim (0 ≤ aij ≤ 106)。
输出
打印一个数字——问题的答案。
示例
输入 #1
4 5 abcde abcde abcde abcde 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #1
3
输入 #2
4 3 abc aba adc ada 10 10 10 10 1 10 10 10 10 10 1 10
输出 #2
2
输入 #3
3 3 abc ada ssa 1 1 1 1 1 1 1 1 1
输出 #3
0