Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Highest Difficulty Level

Limits 1s, 512 MB

The best rank of any teams from BRAC University in any of the ACM-ICPC Asia Dhaka Regional Contests is 23. This rank has been achieved by team BRACU StrawHats in 2016.

In The 2016 ACM-ICPC Asia Dhaka Regional Contest, there was 10 problems. Each of the problems has a distinct difficulty level. The easiest problem has a difficulty level of 0 and the hardest problem has a difficulty level of 9. The solution to a problem requires the knowledge of one or more algorithms. A team consisting of 3 members is able to solve a problem if the members have the knowledge of all the algorithms required to solve that problem.

For example: Problem A requires the knowledge of Sieve and BFS. A team is able to solve this problem if any of the members of the team has the knowledge of Sieve and this member or any of the other 2 members have the knowledge of BFS.

Given the algorithms known to the members of BRACU StrawHats and the algorithms required to solve the problems of the The 2016 ACM-ICPC Asia Dhaka Regional Contest, your task is to determine the difficulty level of the problem having the highest difficulty level solvable by BRACU StrawHats.

Input

The input consists of 13 lines, each containing a string. The first 3 lines represent the members of BRACU StrawHats and the last 10 lines represent the problems (starting with the easiest problem and ending with the hardest problem). A character within a string represents an algorithm. In case of the members, this is an algorithm the member has knowledge of and in case of the problems, this is an algorithm that is required to solve it.

Output

You need to print the difficulty level of the problem having the highest difficulty level solvable by BRACU StrawHats. In case that none of the problems is solvable by BRACU StrawHats, print -1.

Constraints

1 ≤ size of string ≤ 5
all characters of the strings ∈ [A-Z]

Samples

InputOutput
A
B
C
AD
D
ACD
BGHY
BE
CBAU
GTY
HG
BKO
T
-1
InputOutput
A
B
C
AD
D
ABC
BGHY
BE
CBAU
GTY
HG
BKO
T
2

Discussion