問題文
A、T、G、C 中的任意一个字符以及每个 1 字符对应的通配符(.)构成的字符串模式 N 。
1 每个模式最多 1 只能包含一个通配符。
包含所有给定模式作为子字符串的字符串 X 中最短的长度是多少,吉野君。
入力
输入是按以下格式从标准输入给出的。
N S1 S2 : SN
- 1第 行表示模式数量 N(1 \leq N \leq 12) 。 表示
- 2从行 N 行包含i第几个模式 Si 。 表示
- Si 的长度 |Si| 是 您也可以写 1 \leq |Si| \leq 600 很满意。
- Si 由 A、T、G、C 中的任意字符或通配符(.)组成。
- Si 中包含的通配符数量最多为 1 字符。
部分点
- 如果所给模式中所有模式都不包含通配符且答对的情况,将作为部分分数给出 60 分。
出力
输出最短的字符串 X 的长度 1 行。在输出末尾添加换行符。
入力例1
2 TAG GAT
出力例1
5
输出最短的字符串 X 是
您也可以写 TAGAT或
至少GATAG。
入力例2
4 AA. TAT ATTAC. TA.T
出力例2
9
输出最短的字符串 X 是
您也可以写 AATTACTAT 。