Problem Description

You are given N patterns consisting of one of the characters A, T, G, C and a wildcard (.) that matches any single character.

Each pattern contains at most one wildcard.

Find the length of the shortest string \( X \) that contains all given patterns as substrings, Yoishio.

Input Format

The input is given from the standard input in the following format:

\( N \) \( S1 \) \( S2 \) \( : \) \( SN \)

Output Format

Output the length of the shortest string \( X \) in one line. Make sure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

2
TAG
GAT

Sample Output #1

5

Sample Input #2

4
AA.
TAT
ATTAC.
TA.T

Sample Output #2

9

Notes/Hints

Partial Points

• If you correctly solve the case where none of the given patterns contain a wildcard, you will be awarded 60 points as partial credit.

Sample Explanation 1

The shortest string \( X \) is either TAGAT or GATAG.

Sample Explanation 2

The shortest string \( X \) is AATTACTAT.

见题面 Input 部分

见题面 Output 部分