물약
면접 대비시간 제한2초메모리 제한128 MB
시장 재료의 가격과 제조 레시피가 주어질 때, LOVE라는 물약 1단위를 만드는 최소 비용을 구한다.
문제
마법의 물약은 다음과 같은 조합식으로 만들 수 있다.
S = N1×S1 + ... + Nk×Sk
여기서 각 Ni는 1 이상 9 이하의 한 자리 숫자이고, 각 Si는 재료의 이름이며, k는 1 이상의 자연수이다. 이 식은 S1을 N1만큼, ..., Sk를 Nk만큼 넣으면 물약 S를 1만큼 만들 수 있다는 뜻이다.
같은 물약을 만드는 조합식이 여러 개 있을 수 있으며, 그중 아무 조합식이나 사용할 수 있다. 어떤 물약은 다른 물약의 재료가 될 수도 있고, 일부 재료는 시장에서 살 수 있다.
시장에 파는 재료와 가격, 그리고 사용할 수 있는 모든 조합식이 주어진다. 이름이 LOVE인 마법의 물약을 1만큼 만드는 데 드는 최소 비용을 구하라.
입력
첫째 줄에 시장에서 파는 재료의 개수 N과 사용할 수 있는 물약 조합식의 개수 M이 주어진다.
다음 N개의 줄에는 시장에서 파는 재료의 이름과 가격이 공백으로 구분되어 주어진다. 재료의 이름은 알파벳 대문자로만 이루어져 있으며, 시장에서 파는 재료의 이름은 중복되지 않는다.
그다음 M개의 줄에는 위에서 설명한 형식의 조합식이 공백 없이 주어진다.
N은 50 이하의 자연수이다. M은 0 이상 50 이하의 정수이다. 재료 이름의 길이는 최대 50이고, 가격은 100 이하의 자연수이며, 각 조합식의 길이는 최대 50이다.
출력
LOVE를 1만큼 만드는 데 드는 최소 비용을 출력한다.
최소 비용이 1,000,000,000보다 크다면 1000000001을 출력한다. LOVE를 만들 수 없다면 -1을 출력한다.