시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 263 14 12 11.111%

문제

과학자 임문빈은 마법의 물약을 만든다. 임문빈은 많은 재료를 가지고 있고, 다음과 같은 식을 이용해서 만든다.

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

여기서 N1, ..., Nk는 1보다 크거나 같고, 9보다 작거나 같은 한 자리 숫자이고, S1, ..., Sk는 재료의 이름이다. 그리고, k는 1보다 크거나 같은 자연수이다. 마지막으로 S는 마법의 물약의 이름이다. 위의 식은 N1만큼 S1을 넣고, ..., Nk만큼 Sk를 넣으면 S가 1만큼 만들어 진다는 얘기와 같다.

같은 물약을 만드는데 여러가지 재료법이 있을 수도 있다. 이 때는, 아무거나 사용하면 된다. 마법의 물약은 또 다른 물약을 만드는데 재료가 될 수도 있고, 이 중 어떤 재료는 시장에서 살 수 있다.

임문빈은 이름이 LOVE인 마법의 물약을 만들려고 한다. (이 물약을 먹으면 임문빈을 사랑하게 된다) 시장에서 파는 재료와 그 가격이 주어지고, 임문빈이 만들 수 있는 모든 물약의 식이 주어진다. 이 때, LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다.

입력

첫째 줄에 시장에서 파는 재료의 개수 N과 임문빈이 만들 수 있는 물약의 식의 개수 M이 주어진다. 둘째 줄 부터 N개의 줄에는 시장에서 파는 재료의 이름과 그 가격이 공백으로 구분해서 주어진다. 재료의 이름은 오직 알파벳 대문자로만 이루어져 있고, 파는 재료는 중복되지 않는다. 그 다음 줄 부터 M개의 줄에는 물약의 식이 문제 상단과 같은 형식으로 주어진다. N은 50보다 작거나 같은 자연수이고, 재료의 이름의 길이는 최대 50이다. 가격은 100보다 작거나 같은 자연수이다. M은 50보다 작거나 같은 자연수 또는 0이다. 각 식의 길이도 최대 50이다.

출력

첫째 줄에 LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다. 만약 그 값이 1000000000보다 크다면 1000000001을 출력한다. 만약 LOVE를 만드는 것이 불가능 하다면 -1을 출력한다.

예제 입력

3 2
WATER 2
HONEY 6
HOP 9
LOVE=2WATER+4HONEY+2BEER
BEER=1HOP+3WATER+1HOP

예제 출력

76

힌트

출처