스크리블

그는 유가(yuga)의 중반에 이르러 캘러사이(calathi)에 플롱(flong)을 넣었으나, 그것은 무산되었다.

응?

믿기 어렵겠지만 위 문장은 문법적으로 완전히 올바른 영어 문장이다. 이 문장에는 두 가지 특징이 더 있다. 스팸처럼 보인다는 것, 그리고 단어 하나하나의 점수가 매우 높다는 것이다.

점수가 높다고? (무슨 이유에서인지 오늘따라 자꾸 혼잣말을 하고 있다.)

그렇다 — 스크리블(Scribble) 게임을 한다면 이 단어들은 아주 값지다. 표준 스크리블에서 calathi("그리스 회화와 조각에 등장하는 꽃병 모양의 바구니")는 $72$점, nixed("거절당한")는 $26$점, flong("스테레오타이프 판의 주형이 되는, 압축된 종이 뭉치")은 $18$점, yuga("힌두 전통에서 세계의 존속 기간을 나누는 네 시대 — 크리타(사티아), 트레타, 드와파라, 칼리 — 중 하나")는 $33$점이다.

알다시피 스크리블에서 각 글자에는 정해진 점수가 있으며, 주어진 글자들로 가능한 한 높은 점수를 얻는 것이 목표다.

이 문제에서는 규칙을 조금 바꾼다. 당신에게는 $7$개의 타일(글자)이 있고, 각 글자 $\alpha$에는 점수 $s_\alpha$가 있으며 $0 \le s_\alpha \le 26$을 만족한다. 또한 (일반적인 스크리블과 달리) 게임을 하기 전에 유효한 단어들의 사전을 참고할 수 있다. 당신의 임무는 만들 수 있는 가장 높은 점수의 단어를 찾는 것이다. 한 단어의 점수는 그 단어를 이루는 글자들의 점수 합이다.

첫 번째 줄에 정수 $k$ ($1 \le k \le 7$)가 주어진다. 이어지는 $k$개의 줄에는 각각 세 값 $\alpha\ s_\alpha\ r_\alpha$가 주어진다. 여기서 $\alpha$는 글자, $s_\alpha$는 그 글자의 점수, $r_\alpha$는 그 글자가 적힌 타일의 개수이다. $\sum_\alpha r_\alpha = 7$임이 보장된다. 예를 들어 세 값 a 7 2는 각각 $7$점짜리 a 타일이 두 개 있다는 뜻이다. 그다음 줄(즉 $k+2$번째 줄)에는 정수 $N$ ($0 \le N \le 100\,000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 단어가 하나씩 주어지며, 각 단어의 길이는 최소 $1$이다.

한 줄에 정수 하나를 출력한다. 이는 최대 점수, 즉 가진 타일로 사전에 있는 완전한 단어 하나를 만들어 얻을 수 있는 최대 점수이다. 어떤 단어도 만들 수 없다면 $0$을 출력한다.