Son of Durin

Thorin wants to collect as many gold coins as he can before winter arrives. He has a map of the tunnels inside the mountain. The map marks the caves that hold gold coins, and it also records how many coins each cave holds.

The map is an $N \times M$ grid. Each cell holds one of these characters.

• . an empty cell Thorin can walk on
• # a wall. Thorin cannot enter it and cannot cross it
• ^ a teleport site
• d the cell where Thorin starts. Exactly one cell of the map holds it
• 0 through 9 and A through F a cave. Read the character as a hexadecimal digit to get the cave number. Numbering starts at 0, so 0, 3, and B are caves 0, 3, and 11

In one unit of time Thorin moves to one of the four cells adjacent up, down, left, or right, as long as that cell is not a wall. While he stands on a ^ cell he can spend one unit of time to teleport to any other ^ cell of the map. He can also walk off a ^ cell to an adjacent cell in the usual way. He can teleport at most $P$ times in total.

The moment Thorin enters a cave he takes all of its coins. Taking the coins costs no time. Entering a cave he has already emptied gives him nothing more. He may pass through the same cell any number of times.

Compute the largest number of coins Thorin can collect within $L$ units of time while teleporting at most $P$ times.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains four space separated integers $N$, $M$, $P$, and $L$ ($1 \le N, M \le 500$, $0 \le P \le 10^5$, $0 \le L \le 10^9$). $N$ is the number of rows of the map, $M$ is the number of columns, $P$ is the limit on teleports, and $L$ is the limit on time.

Each of the next $N$ lines contains $M$ characters and gives one row of the map.

The last line contains the coin counts of the $K$ caves in order, starting with cave 0, separated by spaces. Each count is between 0 and $10^9$. The cave numbers that appear on the map are exactly 0 through $K-1$, and no number appears twice ($1 \le K \le 15$).

For each test case print the largest number of coins Thorin can collect, one per line.