ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Making Potions

Задачи раздела

• Making Potions
• Santa Gifts
• Chessboard Pattern
• 10^6
• A + B
• A+B
• Amuz Deluxe
• C++ и Java
• Captcha

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма

An old witch is making a love potion. She has a lot of recipes and each of them has the following form:

S = N1 · S1 + ... + Nk · Sk (1)

where Ni are single-digit integers between 1 and 9, inclusive, Si are names of ingredients, k is an integer greater than or equal to 1, and S is name of the resulting potion (all names contain only uppercase letters). This means that if she mixes N1 units of S1, ..., Nk units of Sk all together, she will obtain 1 unit of S. There may be multiple recipes for the same potion. In that case, the potion can be obtained using any one of them. The ingredients are also potions, and some of them can be bought at the market.

You want to create 1 unit of the potion called LOVE. You are given M recipes, and each recipe is formatted as described above. You are also given L market goods with their costs. Return the cheapest cost of obtaining 1 unit of LOVE. If this cost is greater than 1,000,000,000, return 1000000001 instead. If the potion cannot be obtained, return -1 instead.

Input
The first line contains two numbers L and M (1 ≤ L ≤ 50, 0 ≤ M ≤ 50). Next L lines will contain names of market goods. Each name will contain only uppercase Latin letters ('A' - 'Z'). All names will contain between 1 and 50 characters, inclusive. Next L lines will contain the costs of these goods, one per line, each cost between 1 and 100, inclusive. Next M lines will contain recipes in the format described above, each recipe will contain only uppercase Latin letters ('A' - 'Z'), non-zero digits ('0'-'9') and characters '+' and '=', each recipe will contain between 4 and 50 characters inclusive.
Output
Output single number - the cheapest cost to produce one unit of the potion LOVE. If this cost is greater than 1,000,000,000, output 1000000001 instead. If the potion cannot be obtained, output -1 instead.

Input 1 Input 2
3 1
LOVE
WATER
HONEY
100
1
30
LOVE=5WATER+3HONEY
3 2
WATER
HONEY
HOP
2
6
9
LOVE=2WATER+4HONEY+2BEER
BEER=1HOP+3WATER+1HOP
Output 1 Output 2
95
76
Input 3 Input 4
2 1
ORANGEJUICE
APPLEJUICE
6
4
JUICEMIX=1ORANGEJUICE+1APPLEJUICE
3 2
WATER
HONEY
HOP
1
22
17
LOVE=7WATER+3HONEY
LOVE=2HONEY+2HOP
Output 3 Output 4
-1
73

Для отправки решений необходимо выполнить вход.

www.contester.ru