Potion

A magical potion can be made from a recipe of this form:

S = N1×S1 + ... + Nk×Sk

Here, each Ni is a one-digit number from 1 to 9, each Si is an ingredient name, and k is at least 1. The formula means that adding N1 units of S1, ..., and Nk units of Sk produces 1 unit of the potion S.

There may be several recipes for the same potion; any one of them may be used. A potion can also be an ingredient for another potion, and some ingredients can be bought at the market.

Given the market ingredients with their prices and all available recipes, find the minimum cost needed to make 1 unit of the magical potion named LOVE.

The first line contains two integers N and M: the number of ingredients sold at the market and the number of available potion recipes.

Each of the next N lines contains the name of a market ingredient and its price, separated by a space. Ingredient names consist only of uppercase English letters, and no market ingredient name is repeated.

Each of the next M lines contains one recipe in the format described above, with no spaces.

N is a positive integer no greater than 50. M is an integer from 0 to 50. Each ingredient name has length at most 50, each price is a positive integer no greater than 100, and each recipe line has length at most 50.

Print the minimum cost needed to make 1 unit of LOVE.

If the minimum cost is greater than 1,000,000,000, print 1000000001. If LOVE cannot be made, print -1.