연금술의 안전

프레데리코 데 빈치(레오나르도의 재능이 조금 부족한 사촌 중 한 명)는 납을 금으로 바꾸는 공식을 우연히라도 찾아내길 바라며 매일 온갖 화학 물질을 섞는 풋내기 연금술사입니다. 작업대 옆에는 값싼 도자기 항아리를 두고, 실패한 실험에서 나온 쓸모없고 다소 유독한 결과물을 그곳에 버립니다.

항아리에 넣은 화학 물질들이 서로 반응하며 내는 열 때문에, 그는 처리용 항아리가 금이 가거나 산산조각 나는 사고를 몇 번 겪었습니다.

프레데리코는 과거에 항아리에 함께 넣어 본 여러 화학 물질 쌍이 만들어 내는 온도 변화를 표로 정리해 두었습니다. (그는 화학 물질 3종 이상이 동시에 상호작용하는 경우는 무시해도 좋다고 믿습니다.) 표는 각 쌍에 대해, 첫 번째 물질 1그램이 두 번째 물질 1그램과 반응할 때 오르는 온도를 정수 도(degree) 단위로 알려 줍니다. 이 반응 한 번은 각 물질을 1그램씩 소모하며, 어떤 물질이든 1그램은 이러한 반응에 많아야 한 번만 참여할 수 있습니다.

이 표와, 프레데리코가 항아리에 넣으려는 화학 물질 목록(각각의 수량 포함)이 주어질 때, 항아리 속 내용물이 만들어 낼 수 있는 최대 총 온도 상승량을 구하는 프로그램을 작성하세요.

입력은 하나 이상의 문제 집합으로 이루어집니다. 마지막 문제 집합 뒤에는 ENDOFINPUT 이라는 단어만 있는 줄이 옵니다.

각 문제 집합은 먼저 최대 64개의 화학 물질 쌍과 그 쌍이 내는 열의 목록으로 시작합니다. 각 줄의 형식은 다음과 같습니다.

chemical1 chemical2 heat

여기서 chemical1, chemical2는 각각 길이 1~20의 알파벳 문자열로 된 화학 물질 이름이고, heat는 0 이상 100 이하의 정수로, chemical1 1그램이 chemical2 1그램과 반응할 때 항아리의 온도가 오르는 도 수입니다. 한 줄에서 두 이름이 나오는 순서는 상관없으며, 같은 쌍이 두 번 이상 나오지는 않습니다. 이 목록은 0 0 0 만 있는 줄로 끝납니다.

그다음에는 프레데리코가 항아리에 넣으려는 화학 물질이 최대 12개까지 나열됩니다. 각 줄의 형식은 다음과 같습니다.

chemical amount

여기서 chemical은 화학 물질 이름(역시 길이 1~20의 알파벳 문자열)이고, amount는 0 이상 1000 이하의 정수로 버릴 양(그램)입니다. 같은 화학 물질이 이 목록에 두 번 이상 나오지는 않습니다. 이 목록은 0 0 만 있는 줄로 끝납니다.

각 문제 집합마다 다음 형식의 한 줄을 출력합니다.

The temperature in the jar will change by at most M degrees.

여기서 M은 최대 총 온도 상승량으로, 정수입니다.