Problem E: 英語の勉強

Problem Statement

会津合宿に参加予定の高槻さんは勉強熱心で、最近は英語の勉強をがんばっている。彼女は、携帯を使って次のようなゲームをプレイすることで、少しでも多く英単語を覚えようとしている。彼女が持っている携帯は、指で画面を操作するタッチパネル式である。

携帯の画面には、4 * 4のマス目が描かれており、各マスにはアルファベット大文字が書かれている。このゲームは、制限時間T秒の間に、マス目の中に隠されている英単語をたくさん見つけ、発見できた英単語の種類により点数を競うものである。

1つの単語を見つける手順は、次のようになる。まず、単語の1文字目に対応する開始マスを決めて、そこに指を置く。そして、今指を置いているマス目から、上下左右・斜めの、隣接する8方向のマスのいずれかに向かって、指でなぞっていく。ただし、開始マスから現在のマスまですでに辿ったことがあるマスは、通ることができない。単語の終了マスに達したら、そこで指を離す。その瞬間、開始マスから終了マスまで指でなぞった単語1つの点数が加点される。x文字の単語1つをなぞるためには、x秒の時間がかかる。ある単語をなぞってから、次の単語をなぞるための指の移動時間は無視してよい。

入力では、加点対象となる単語の辞書も入力される。この辞書の各単語には、点数が振られている。辞書の中に書かれている単語を指でなぞると、その単語に対応する点数が加算される。ただし、開始マスから終了マスまで、全く同じ指のなぞり方をした単語は、最初の1回しか点数加算されない。辞書に書かれていない単語を指でなぞっても加点はされない。

辞書とゲームの盤面が与えられるので、制限時間内に得られる最大の点数を出力せよ。

Input

各データセットは、以下の形式で入力される。

N
word1 score1
word2 score2
...
wordN scoreN
line1
line2
line3
line4
T

Nは、辞書に含まれる単語の数を表わす整数である。続いてN行にわたって、辞書が入力される。wordiは1つの単語を表わすアルファベット大文字で構成される文字列、scoreiはwordiの単語を指でなぞったときに得られる点数を表わす整数である。辞書の中に、同じ単語が2回以上現れることはない。

続いて4行にわたって、各マス目の文字が入力される。lineiは、4文字のアルファベット大文字だけで構成される文字列である。lineiの左からj文字目は、i行目の左からj番目の文字に対応する。

一番最後に、制限時間を表わす整数Tが入力される。

Constraints

• 1 <= N <= 100
• 1 <= wordiの文字列長 <= 8
• 1 <= scorei <= 100
• 1 <= T <= 10000

Output

制限時間内に取得できる最高の点数を1行で出力せよ。

Sample Input 1

6
AIZU 10
LINER 6
LINE 4
ALL 2
AS 1
CIEL 10
ASLA
CILI
IRZN
ELEU
21

Output for the Sample Input 1

40

図1に操作例を示す。例えば、次のようになぞると40点となる。

• "CIEL"は、文字列の長さが4であるため4秒かけて10点。
• "AIZU"は、違うなぞり方をすれば、2つ発見できるため、8秒かけて20点。
• "LINER"ã‚’5秒かけて6点。
• "LINE"ã‚’4秒かけて4点。