メイズ＆アイテムは、アイテムを回収しながら、ゴールを目指すパズルゲームである。迷路は $W \times H$ 個のマスから成り、持っているアイテムによって、入れるマスと入れないマスがある。また、アイテムの回収順序によって定められた得点を獲得することができる。ゲームの目的は、スタート地点から出発し、全てのアイテムを回収し、最小の移動回数でゴール地点に到達することである。最小の移動回数でゴール地点に到達できる経路が複数ある場合は、最大の得点で到達することを目指す。
各マスには以下のいずれかの記号が割り当てられている。あなたは以下のルールで、縦または横の辺を共有するマスに移動することができる。ただし、迷路の外側を移動先として選ぶことはできない。
| 記号 | 意味 |
|---|---|
| . | 常に入ることができるマス。 |
| # | 常に入ることができないマス。 |
| 数字：0, 1,.., 9 | アイテムがあるマス。数字がアイテムの番号を表す。常に入ることができる。 |
| 大文字：A, B, ..., J | 対応するアイテムを持っていないときだけ入ることができるマス。A, B, ..., J がそれぞれ 0, 1, ..., 9 に対応する。 |
| 小文字：a, b, ..., j | 対応するアイテムを持っているときだけ入ることができるマス。a, b, ..., j がそれぞれ 0, 1, ..., 9 に対応する。 |
| S | スタート地点のマス。常に入ることができる。 |
| T | ゴール地点のマス。常に入ることができる。 |
ゴール地点に到達しても、すべてのアイテムを持っていないとゲームの目的を達成することはできない。また、アイテムがあるマスに入った場合は、回収するかどうかを選ぶことができる。回収したアイテムはマスから消える。一度回収したアイテムは持ち続けなければならない。
迷路の状態と、２つのアイテムを回収した順序によって得られる得点の表が与えられたとき、全てのアイテムを回収しゴール地点にたどり着くための、最小の移動回数とそのときに得られる最大の得点を出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$W$ $H$
$row_1$
$row_2$
...
$row_H$
$s_{00}$ $s_{01}$ ... $s_{09}$
$s_{10}$ $s_{11}$ ... $s_{19}$
...
$s_{90}$ $s_{91}$ ... $s_{99}$
１行目に迷路の横方向と縦方向のマスの数$W$ ($4 \leq W \leq 1000$)と$H$ ($4 \leq H \leq 1000$)が与えられる。続く$H$行に、迷路の上から$i$行目に並んだマスの情報$row_i$が与えられる。$row_i$は、それぞれ長さが$W$であり、上の表で定められた記号からなる文字列である。１文字が１つのマスを表す。続く10行にアイテムを回収した順序によって得られる得点の表が与えられる。$s_{ij}$ ($0 \leq s_{ij} \leq 100$)は、アイテム$i$の次に回収したアイテムがアイテム$j$であるときに得られる得点を表す整数である。ただし、$s_{ii} = 0$である。
マスの情報は以下の条件を満たす。
- S, T, 0, 1, ..., 9 は迷路の中にそれぞれちょうど１つ存在する。
- A, B, ..., J, a, b, ..., jは迷路の中にそれぞれ高々１つ存在する。
出力
最小の移動回数とそのときに得られる最大の得点を、空白区切りで１行に出力する。ただし、ゲームの目的を達成することができない場合は「-1」をひとつだけ１行に出力する。
入出力例
入力例１
12 5 .....S...... .abcdefghij. .0123456789. .ABCDEFGHIJ. .....T...... 0 1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例１
26 2
入力例２
4 5 0jSB ###. 1234 5678 9..T 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例２
31 0
入力例３
7 7 1.3#8.0 #.###.# #.###.# 5..S..9 #.#T#.# #.###.# 4.2#6.7 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例３
53 19
入力例４
5 6 ..S.. ##### 01234 56789 ##### ..T.. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例４
-1