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.
Samples
| Input | Output |
|---|---|
A B C AD D ACD BGHY BE CBAU GTY HG BKO T | -1 |
| Input | Output |
|---|---|
A B C AD D ABC BGHY BE CBAU GTY HG BKO T | 2 |
