HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Strings > problem:


50246 - Making Potions

Guest
• Discussion of problem (1)

Section problems

• 50323 - Filtering Contact List
• 50555 - Frequency of Letters
• 50655 - Divisibility by 9
• 50656 - Divisibility by 11
• 50767 - Censor
• 50762 - Rare name
• 50760 - Hexatridecimal Sum
• 50761 - Magic Words
• 50246 - Making Potions
• 50768 - Where is Waldorf?

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Difficulty Gamma

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