Crabbles

제니퍼는 Crabbles 대회를 준비하고 있습니다. 그녀는 주머니에서 Crabbles 타일 한 움큼을 꺼내, 가능한 한 높은 점수의 단어를 만들려고 합니다. 각 타일에는 글자(단어를 만드는 데 사용) 하나와 숫자(그 타일의 점수) 하나가 적혀 있습니다. 각 타일은 한 단어 안에서 최대 한 번만 사용할 수 있으며, 모든 타일을 반드시 사용할 필요는 없습니다. 만든 단어는 반드시 그녀의 사전에 있는 단어여야 합니다. 점수는 단어에 사용한 타일들의 점수를 모두 더한 값입니다.

Crabbles에서는 같은 글자가 적힌 서로 다른 타일이라도 점수가 다를 수 있다는 점에 유의하세요.

제니퍼가 결과를 확인할 수 있도록, 주어진 타일 집합으로 얻을 수 있는 최대 점수를 알려 주는 프로그램을 작성하세요.

첫째 줄에 사전에 있는 단어의 수 $N$ ($1 \le N \le 100{,}000$)이 주어집니다. 이어지는 $N$개의 줄에는 사전 단어가 한 줄에 하나씩 주어지며, 각 단어는 소문자 알파벳으로만 이루어져 있습니다. 그다음 줄에는 제니퍼가 진행할 손패(hand)의 수 $M$ ($1 \le M \le 1{,}000$)이 주어집니다. 이어서 $M$개의 손패가 주어집니다. 각 손패는 그 손패에 있는 타일의 수 $P$ ($1 \le P \le 10$)가 적힌 줄로 시작하고, 그 뒤로 $P$개의 줄이 이어집니다. 각 줄에는 타일의 글자(소문자 하나), 공백, 그리고 그 타일의 점수 $V$ ($0 \le V \le 10$)가 순서대로 주어집니다.

각 손패에 대해, 그 손패로 만들 수 있는 최대 점수를 한 줄에 하나씩 출력하세요. 만들 수 있는 단어가 하나도 없으면 $0$을 출력합니다.