Enterprise Escape

The Enterprise is surrounded by a Klingon fleet. Find the fastest way out and report how long it takes.

You are given a rectangular grid. Each cell holds either the Enterprise or one Klingon warship. The warships are divided into classes, and each class takes a fixed amount of time for the Enterprise to disable.

The Enterprise moves only to a neighbouring cell that shares an edge, so a cell has at most four neighbours and a diagonal move is not allowed. Every time it enters a new cell it must disable the warship standing there, which costs that class's time. The starting cell costs nothing.

Call a cell an edge cell when it lies in the first row, the last row, the first column, or the last column. Once the Enterprise reaches an edge cell and disables the warship there, it leaves the grid at no extra cost. If it already stands on an edge cell, it escapes right away and the time is 0.

The first line has the number of test cases T (2 ≤ T ≤ 100).

The first line of each test case has three integers K, W, and H. K (1 ≤ K ≤ 25) is the number of Klingon warship classes, W (1 ≤ W ≤ 1000) is the width of the grid, and H (1 ≤ H ≤ 1000) is its height.

The next K lines each hold a class name and the time needed to disable that class, separated by a space. A class name is a single uppercase letter and is never "E". No name appears twice. The time is given in minutes and is an integer between 0 and 100,000.

The next H lines each hold W uppercase letters with no spaces between them. "E" is the position of the Enterprise and appears exactly once in the whole grid. Every other letter is the class of the Klingon warship in that cell, and it always appears among the K lines above.

For each test case, print the minimum time the Enterprise needs to escape as an integer on its own line.