Practice on Toph

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

Lucky String

By amin21 · Limits 1s, 256 MB

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 -

  1. Pick k number of octal-string from the given List and erase them from this list. (You can not pick any erased octal-string).
  2. Generate a new string by concatenating the picked octal-string.
  3. 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

InputOutput
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.

    Discussion

    Statistics


    27% Solution Ratio

    AashiqEarliest, 3M ago

    AungkurFastest, 0.1s

    DalgerokLightest, 3.8 MB

    zishan044Shortest, 1337B

    Submit

    Login to submit

    Editorial

    maximum number of sorted subset of 13 length octal-string wile be 1948. then this can be solve by 1...

    Related Contests