You are given the string S, and the set of strings [mathcal]P whose size is N. Now we consider applying the following operation to S:
Let si be a i-th character of S, Sij be a consecutive substring in S such that S=sisi+1 ⋯ sj, and pk as the k-th string of P. Your task is to calculate the minimum number of operations for satisfying the following condition.
An input is given in the following format.
S N p1 p2 ⋮ pN
Print the minimum number of operations in one line.
brainfuck 1 fuck
1
For example, if you change "brainfuck" into "brainf*ck", you can satisfy the condition. You have to perform operation at least once, and it is the minimum value.
aaa 1 a
3
You have to operate for all characters.
hellshakeyano 3 hell shake key
2
In this case, for example, if you change "hellshakeyano" into "h*llsha*eyano", you can satisfy the condition. Notice if you replace one character, it might happen that several strings in the set P, which appear as the consecutive substring of S, simultaneously disappear.