C - シークエンサー

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

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

最短の文字列 XTAGATまたはGATAGです。


入力例2

4
AA.
TAT
ATTAC.
TA.T

出力例2

9

最短の文字列 XAATTACTAT です。


Source Name

天下一プログラマーコンテスト2014 本戦