Oscar's Ransom Note

Oscar loves crime movies and admires the creativity of criminals. He wants to show his own creativity by preparing a ransom note. However, instead of cutting individual letters from newspapers as in the movies, he plans to cut out entire words from newspapers and assemble them to form his note.

The newspapers provide him with a set of words (repetition allowed), but some words in his desired ransom note might not appear in the newspapers at all. To simplify his task, Oscar removes all punctuation and spaces from his target ransom note and ignores letter case. Moreover, he is allowed to let the cut-out words overlap, as long as the overlapping parts exactly match.

Your task is to help Oscar determine the minimum number of words he needs to cut out from the newspapers to assemble his ransom note. If it is impossible, output -1.

Overlapping Explanation: Suppose you have already covered a part of the note up to index i. When placing a new word w (of length L) with an overlap of r characters (0 ≤ r ≤ min(i, L)), the following must hold:

T[i - r, i - 1] = w[0, r - 1] \quad and \quad T[i, i + (L - r) - 1] = w[r, L - 1]

The new word then extends the covered segment to index i + L - r.

inputFormat

The input is given in the following format:

T
n
w1
w2
... 
wn

Where:

• T is a string representing the target ransom note (with punctuation removed and in a uniform case).
• n is an integer representing the number of available newspaper words.
• w1, w2, ..., wn are the words available in the newspapers. Each word can be used any number of times.

Note: The words in the note and in the newspaper are composed only of letters.

outputFormat

Output a single integer representing the minimum number of words needed to form the ransom note. If it is impossible, output -1.

sample

abcab
3
ab
bc
ca

3