Jimin Kim's Invasion

The kingdom ruled by Im Hansu is threatened by an invasion led by the rebel Jimin Kim. Jimin Kim's army is trying to enter the capital from every boundary of the kingdom. To block every route to the capital, Im Hansu plans to place obstacles on some cells of the map.

The map is an N by M rectangular grid. The capital is marked with *, cells that are already impassable are marked with -, and every other cell is an uppercase English letter representing its terrain. The army can move only up, down, left, or right to an adjacent cell sharing an edge.

Obstacles can be placed on terrain cells marked by uppercase letters, and each terrain type has a required obstacle size. Every path from a boundary cell to the capital must be blocked by either - cells or newly placed obstacles. First minimize the number of obstacles placed. If there are several ways to do so, choose one with the minimum total obstacle size. Find that total size.

The first line contains N and M. Both N and M are natural numbers between 3 and 50, inclusive.

The next N lines contain the map. The last line contains 26 integers. The first integer is the obstacle size required for terrain A, the second for terrain B, and so on in alphabetical order.

There is exactly one capital, and it is not in the first row, last row, first column, or last column. Every obstacle size is between 1 and 1,000,000, inclusive.

Print the total size of the obstacles installed under the required conditions.