Problema C - Palavras para que te quero

O Aniceto está muito divertido com o novo jogo que descobriu, o "Palavras para que te quero". A ideia do jogo é muito simples. Tudo começa com uma enorme sequência de letras e um dicionário contendo palavras, bem como uma pontuação atribuída a cada uma dessa palavras. Em cada passo o Aniceto escolhe uma subsequência contígua de letras que corresponda a uma palavra do dicionário e marca como usadas as letras correspondentes na sequência inicial. Depois prossegue de forma igual para as letras que restam até não conseguir escolher mais nenhuma palavra da sequência. A pontuação obtida é igual à soma das pontuações de cada uma das palavras que o Aniceto conseguiu usar na sequência inicial. Repara que podem existir várias maneiras de escolher as palavras e o objectivo é atingir o máximo possível de pontos.

Aqui fica um exemplo de um dicionário com 6 palavras, uma sequência inicial de 14 letras e três maneiras diferentes de escolher as palavras (neste caso o máximo possível é de 11 pontos).

Dicionário:                       Sequência:

Palavra      Pontos               informaticamas
-------------------
         ca | 2
         ti | 1                   3 formas de jogar:
        mas | 2
      camas | 5                   informatica + mas = 6 + 2 = 8
    informa | 5                   informa + ti + camas = 5 + 1 + 5 = 11
informatica | 6                   informa + ti + ca + mas = 5 + 1 + 2 + 2 = 10

A mesma palavra pode ser usada várias vezes, mas nem sempre é possível acabar por usar todas as letras da sequência. Por exemplo, com o mesmo dicionário e a sequência "mtitias" o máximo possível seria 2 pontos, correspondentes a escolher duas vezes "ti". No final sobra "mtitias" (a vermelho as letras já usadas) o que não corresponde a nenhuma palavra (nota que não podes usar o "mas" pois não corresponderia a letras contíguas na sequência inicial).

Consegues ajudar o Aniceto a jogar e descobrir qual a melhor pontuação possível?

O Problema

Dado um dicionário com P palavras, cada uma acompanhada pela respectiva pontuação, e um conjunto de sequências de letras, a tua tarefa é calcular a melhor pontuação possível de atingir para cada sequência, de acordo com as seguintes regras de jogo: em cada sucessiva jogada podes escolher uma subsequência de letras contíguas na sequência inicial que corresponda a uma palavra do dicionário, marcando essas letras na sequência como usadas (significando isto que não poderão ser usadas de novo em jogadas posteriores); o jogo termina quando não é possível escolher mais palavras e a pontuação obtida corresponde à soma das pontuações de cada uma das palavras escolhidas até essa altura.

Input

Na primeira linha vem um número inteiro P, indicando o número de palavras do dicionário (1 ≤ P ≤ 10 000).

Seguem-se exactamente P linhas, cada uma delas contendo uma única palavra e a respectiva pontuação, separadas por um único espaço. Cada palavra é uma sequência de letras minúsculas com um máximo de 100 letras. A pontuação é um número inteiro positivo menor ou igual a 1 000. As palavras podem vir por qualquer ordem e não aparecem palavras repetidas.

Depois vem uma linha contendo um número inteiro C indicando o número de sequências a considerar (1 ≤ C ≤ 10).

Seguem-se exactamente C linhas, cada uma contendo uma sequência de letras minúsculas, que corresponde a uma sequência inicial do jogo a partir da qual queremos escolher as palavras. O tamanho S de cada sequência é tal que 1 ≤ S ≤ 10 000.

Output

O output deve conter exactamente C linhas, uma para cada sequência inicial. Cada linha deve conter um único número inteiro indicando a pontuação máxima possível de obter para a sequência respectiva com o dicionário dado. As sequências devem vir pela mesma ordem do input.

Nota sobre a Avaliação

Para um conjunto de casos de teste valendo 60% dos pontos, o número de palavras P do dicionário é inferior ou igual a 30 e o tamanho S das sequências é inferior ou igual a 15.

Exemplo de Input

6
ca 2
ti 1
mas 2
camas 5
informa 5
informatica 6
2
informaticamas
mtitias

Exemplo de Output

11
2