Advertisement Reuse

Little G runs a small company and plans to advertise using old fence posts. Each fence post is a 4-prism with one 1×L face which is divided into L contiguous 1×1 squares. Each square has a letter pre-printed on it. Little G has many such fence posts in his warehouse — each post is described by a string of length \(L\) (all posts are identical in size; they differ only in the letters printed on them).

Little G reuses the fence posts by stacking them vertically. The posts are arranged in order from top to bottom. When a post is placed, its letters (given in the fixed order) form one row of a panel. Thus, if you stack \(K\) fence posts, you produce a panel of \(K\) rows and \(L\) columns, which contains exactly \(K \times L\) letters. Starting from the top left of the panel, by reading the letters in order (i.e. reading each post’s letters from top to bottom and then moving to the next post) you obtain a long letter sequence.

Little G has already decided on the advertisement text he wants. Without modifying any letters on the fence posts (you are not allowed to change or erase letters individually), he is allowed only to "paint white" (i.e. ignore) some cells so that the remaining letters, read in order, form the desired advertisement word. You are given the target advertisement word and the description of the available fence post types (each type is a string of length \(L\); assume there are infinitely many copies of each type). Determine the minimum number of fence posts that need to be stacked to obtain a panel whose letter sequence has the target word as a subsequence.

If it is impossible to obtain the target word with any number of fence posts, output -1.

Note: When a fence post is used, its letters are read in the given order. You may choose the order in which fence posts are stacked (types may be repeated arbitrarily) to maximize the progress in matching the target word. Formally, let the target word be \(T\) of length \(t\) and the available fence post types be strings \(s\) each of length \(L\). For a post used when you have already matched the first \(i\) characters of \(T\), simulate scanning the string \(s\) from beginning to end. Whenever a character in \(s\) equals \(T[i]\), increment \(i\). After processing \(s\), you will have matched some more of \(T\). The goal is to cover all characters of \(T\) with as few posts as possible.

inputFormat

The input consists of multiple lines:

1. The first line contains a string T, the target advertisement word.
2. The second line contains an integer n (\(1 \leq n \leq 100\)), the number of available fence post types.
3. The following n lines each contain a string of equal length \(L\) (\(1 \leq L \leq 1000\)), describing a type of fence post.

All fence post strings have the same length \(L\) and consist only of uppercase English letters.

outputFormat

Output a single integer — the minimum number of fence posts required to obtain the target advertisement as a subsequence. If it is impossible, output -1.

sample

ZENIT
3
TOEIIZENITKN
AAAAAAAAAAAA
ZZZZZZZZZZZZ

1