|
Лимит времени 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
|
Для отправки решений необходимо выполнить вход.
|