Problema da porção do amor

Problema adaptado de MakingPotions do TopCoder.

Dificuldade única

Uma bruxa deseja fazer uma porção do amor com o menor custo possível. Para executar esta tarefa ela combina diversas porções de um livro de receitas que possui fórmulas no seguinte formato:

S=I0S0+...+InSn

Onde:

• I₀...I_n são números inteiros positivos entre 1 e 9 (apenas um dígito).
• S₀...S_n são nomes de porções ou ingredientes.
• S é a porção resultante.
• todos os nomes de ingredintes/porções estão em letras minúsculas.

Pode haver mais de uma forma de fazer uma porção, neste caso pode-se usar qualquer uma delas.

Os ingredientes podem ser comprados no mercado a um custo.

Faça um programa para auxiliar a bruxa nesta tarefa. O programa deve receber as seguintes informações de entrada:

1. um número inteiro N (0<=N<=100) com o número de ingredientes disponíveis no mercado.
2. N ingredientes, um por linha com no máximo 100 caracteres cada.
3. N inteiros positivos, um por linha com valores entre o limite fechado de 1 e 100.
4. um número inteiro K (1<=K<=100) com o número de formulas disponíveis.
5. K formulas, uma por linha com no máximo 1000 caracteres cada.

A saída deverá ser o menor custo possível para se obter a porção do amor.