Problem Description

This is a single-player game.

At the start of the game, the player's character is born at a certain location in the maze. The player's goal is to control the character to reach one of the exits in the maze (there may be multiple exits).

The maze contains $k$ types of traps (denoted by A, B, C, etc., with the same letter representing the same type of trap). Each type of trap can be either harmful or harmless, and at the beginning of the game, the player does not know which traps are harmful and which are harmless.

Traps of the same type have the same status, meaning that traps denoted by the same letter are either all harmful or all harmless; they do not have mixed statuses. Each combination of trap states has a probability of occurrence. Consider the following example:

When $k=2$, there are two types of traps in the maze, denoted by A and B. There are four possible combinations of trap states:
- A is a harmless trap, B is a harmless trap.
- A is a harmful trap, B is a harmless trap;
- A is a harmless trap, B is a harmful trap;
- A is a harmful trap, B is a harmful trap;

The following table is a valid probability table:

When $k=3$, there will be $8$ different combinations of trap states. If we continue to use a probability table, it will be three-dimensional ($2 \times 2 \times 2$, with each dimension corresponding to a type of trap). When $k \geq 3$, this makes the problem difficult to describe. Therefore, we use an array $p$ of size $2^k$ to describe the likelihood of each combination occurring, with indices ranging from $0$ to $2^k - 1$.

$p$ is generated as follows:

For each possible combination of trap states, consider all $k$ types of traps, where $1$ represents a harmful trap and $0$ represents a harmless trap. Treat A as the 0th bit (counting from the right), B as the 1st bit, C as the 2nd bit, etc. Through this operation, we can obtain a $k$-bit binary number, which, when converted to decimal, will correspond one-to-one with integers from $0$ to $2^k - 1$.

Let $S = \sum_{i=0}^{2^k-1} p_i$, then the probability of trap state combination $i$ occurring is $\frac{p_i}{S}$.

The above table corresponds to a valid array $p$ of $36, 24, 24, 16$.

Of course, the same probability table may correspond to multiple arrays $p$ (in fact, there are infinitely many arrays $p$ that can match the table data). For example, the above table also corresponds to the following array $p$: $72, 48, 48, 32$.

The player's character starts with $H$ points of health. When the character steps on a trap, if the trap is harmful, the character loses $1$ point of health; otherwise, the trap is harmless and no health is lost. In either case, the player immediately learns whether the trap is harmful or harmless. Once the health drops to $0$ or below, the character dies immediately.

The maze can be considered as an $m \times n$ grid map, where each element can be:
- . : Represents flat ground, passable;
- # : Represents a wall, impassable;
- A, B, C, etc. : Represents a trap;
- $ : Represents the starting point, there is exactly one in the map;
- @ : Represents the exit, there can be multiple or none in the map.

The character can move up, down, left, or right, but not diagonally or outside the map.

Given the $m \times n$ map, $k$, $H$, and the array $p$ of size $2^k$, your task is to calculate the probability that the character can escape the maze alive under optimal strategy.

Input Format

The first line contains four integers, representing $m, n, k, H$ respectively;

The next $m$ lines, each containing $n$ characters, describe the maze map;

The last line contains $2^k$ non-negative integers describing the array $p$, with indices starting from $0$.

Output Format

Output a single number, representing the probability that the character can escape the maze alive under optimal strategy. Round to three decimal places.

Sample Input and Output

Sample Input #1

4 3 2 1
.$.
A#B
A#B
.@.
30 30 20 20

Sample Output #1

0.600

Sample Input #2

4 3 2 2
.$.
A#B
A#B
.@.
30 30 20 20

Sample Output #2

0.800

Sample Input #3

4 3 2 3
.$.
A#B
A#B
.@.
30 30 20 20

Sample Output #3

1.000

Sample Input #4

4 3 3 2
.$.
A#B
A#C
@@@
143 37 335 85 95 25 223 57

Sample Output #4

0.858

Notes/Hints

[Sample Explanation 1]

Moving to the right, passing B, the probability that B is a harmful trap is $\frac{(20+20)}{(30+30+20+20)} = 0.4$. If B is a harmful trap, the character dies, and the game fails. Otherwise, the player learns that B is harmless, continues to pass another B, and reaches the exit, with a success probability of $0.6$.

[Sample Explanation 2]

Moving to the left, passing A, the probability that A is a harmful trap is $\frac{(30+30)}{(30+30+20+20)} = 0.5$. If A is a harmful trap, the character loses one health point, then tries B to the right. To succeed in reaching the exit, B must be harmless, and given that A is harmful, the probability that B is harmless is $\frac{30}{(30+20)} = 0.6$. Thus, the probability of this scenario is $0.5 \times 0.6 = 0.3$. If A is harmless, the character can pass two As consecutively to reach the exit, with a probability of $0.5$. Therefore, the answer is $0.3 + 0.5 = 0.8$.

[Sample Explanation 3]

The character has $3$ health points but needs to pass at most two traps, so choosing either the left or right path will ensure reaching the exit.

[Data Range and Constraints]

For $100\%$ of the data, $1 \leq m \leq 30$, $1 \leq n \leq 29$, $k \leq 5$, $H \leq 5$, $0 \leq p_i \leq 10^5$, and at least one $p_i > 0$.

见题面 Input 部分

见题面 Output 部分