In your last programming class, you learned about octal number, string concatenation, sorting and greedy methods. That’s why your teacher gives you the following task…………
You are given a List of N number of octal-string (string that contains only ‘0’ to ‘7’). With this List of octal strings, you can create new Lucky string by the following algorithm -
- Pick k number of octal-string from the given List and erase them from this list. (You can not pick any erased octal-string).
- Generate a new string by concatenating the picked octal-string.
- Sort the character of the newly generated string in non-decreasing order. And it is the newly created Lucky string.
Example: If you pick 3 octal-string “74”, “231” and “02” , then the newly generated Lucky string will be “0122347”. You are allowed to create any number of new Lucky string untill the list becomes fully erased.
Now you have to tell What is the minimum number of octal-string is needed to create two new lucky strings S1 and S2. If it is impossible, print -1.
Input
First line contains Lucky String S1
Second line contains Lucky String S2.
Third line contains an integer N (1<=N<=26)
Next N line contain N number of octal-string.
In the whole input set, Maximum length of a single string will be 13 and characters will be sorted in non-decreasing order.
Output
Print a single line of the expected integer.
Sample
| Input | Output |
|---|---|
0345 456 5 035 456 7 4 6 | 3 |
In the first sample, using 1st and 4th octal string you can create first Lucky string and using 2nd octal string you can create 2nd lucky string. So, Using 3 octal-string, you can create 2 lucky string.
