SPOJ Brasil

Emoticons são usados em conversas pela internet e e-mails para tentar expressar as emoções que palavras impressas não conseguem. Isso pode parecer uma coisa boa para muitos, mas muitas pessoas acham eles realmente irritantes e querem se livrar deles.

George é uma dessas pessoas. Ele odeia emoticons tanto, que está preparando um plano para remover todos emoticons de todos os e-mails no mundo. Já que você divide seus planos visionários, você está preparando um programa especial para ajudá-lo.

Seu programa receberá uma lista de emoticons para remover. Cada emoticon será uma string de caracteres não incluindo espaços em branco. Você também receberá diversas linhas de texto. O que você precisa fazer é mudar alguns caracteres do texto para espaços para garantir que nenhum emoticon foi deixado no texto. Para um emoticon aparecer no texto ele tem que aparecer em uma única linha e ser constituído de caracteres consecutivos.

Para que o plano de George permaneça em segredo pelo máximo de tempo possível, você precisa fazer seu trabalho com o mínimo possível de mudanças de caracteres.

Entrada

O arquivo de entrada contém diversos casos de teste. Cada caso de teste consiste de diversas linhas. A primeira linha de cada caso de teste conterá dois inteiros separados por um espaço: N, o número de emoticons para remover, e M, o número de linhas que o texto tem. As próximas N linhas contém um emoticon cada, uma string não-vazia de no máximo 15 caracteres. Cada uma das últimas M linhas do caso de teste contém uma linha de texto com no máximo 80 caracteres. Você pode assumir 1 <= N, M <= 100. Caracteres válidos para emoticons são letras maiúsculas e minúsculas, dígitos e os símbolos “!?.,:;-_’#$%&/=*+(){}[]”. Cada linha de texto pode conter os mesmos caracteres com a adição do caractere de espaço. A entrada acaba com N = M = 0.

Saída

Para cada caso de teste, imprima exatamente uma linha contendo um único inteiro que indica o número mínimo de mudanças que você precisa fazer no texto inteiro para garantir que nenhum emoticon na lista apareça nele.

Exemplo

Entrada
4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0

Saída
11
8