会津合宿に参加予定の高槻さんは勉強熱心で、最近は英語の勉強をがんばっている。彼女は、携帯を使って次のようなゲームをプレイすることで、少しでも多く英単語を覚えようとしている。彼女が持っている携帯は、指で画面を操作するタッチパネル式である。
携帯の画面には、4 * 4のマス目が描かれており、各マスにはアルファベット大文字が書かれている。このゲームは、制限時間T秒の間に、マス目の中に隠されている英単語をたくさん見つけ、発見できた英単語の種類により点数を競うものである。
1つの単語を見つける手順は、次のようになる。まず、単語の1文字目に対応する開始マスを決めて、そこに指を置く。そして、今指を置いているマス目から、上下左右・斜めの、隣接する8方向のマスのいずれかに向かって、指でなぞっていく。ただし、開始マスから現在のマスまですでに辿ったことがあるマスは、通ることができない。単語の終了マスに達したら、そこで指を離す。その瞬間、開始マスから終了マスまで指でなぞった単語1つの点数が加点される。x文字の単語1つをなぞるためには、x秒の時間がかかる。ある単語をなぞってから、次の単語をなぞるための指の移動時間は無視してよい。
入力では、加点対象となる単語の辞書も入力される。この辞書の各単語には、点数が振られている。辞書の中に書かれている単語を指でなぞると、その単語に対応する点数が加算される。ただし、開始マスから終了マスまで、全く同じ指のなぞり方をした単語は、最初の1回しか点数加算されない。辞書に書かれていない単語を指でなぞっても加点はされない。
辞書とゲームの盤面が与えられるので、制限時間内に得られる最大の点数を出力せよ。
各データセットは、以下の形式で入力される。
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が入力される。
制限時間内に取得できる最高の点数を1行で出力せよ。
6 AIZU 10 LINER 6 LINE 4 ALL 2 AS 1 CIEL 10 ASLA CILI IRZN ELEU 21
40
図1に操作例を示す。例えば、次のようになぞると40点となる。