This is a single-player game.

At the start of the game, the player-controlled character spawns at a certain position in a maze, and the player's goal is to control the character to reach one of the exits of the maze (there may be multiple exits). There are $K$ types of traps in the maze (denoted by "A", "B", "C", etc., where the same letter represents the same type of trap). Each type of trap may be harmful or harmless. 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 state; that is, traps marked with the same letter are either all harmful or all harmless; it is impossible for some to be harmful while others are harmless. Every combination of trap states has a probability of occurring. Consider the following example:

When $K=2$, there are two types of traps in the maze, denoted by "A" and "B" respectively. There are 4 possible combinations of trap states: 1. "A" is a harmless trap, "B" is a harmless trap. 2. "A" is a harmful trap, "B" is a harmless trap. 3. "A" is a harmless trap, "B" is a harmful trap. 4. "A" is a harmful trap, "B" is a harmful trap.

A valid probability table is given below:

When $K=3$, there are 8 different combinations of trap states. If we continue to use a probability table, it would be three-dimensional ($2 \times 2 \times 2$, with each dimension corresponding to a type of trap). When $K \ge 3$, this makes the problem difficult to describe. Therefore, we use an array $p$ of size $2^K$ to describe the probability of each situation occurring, where the index of $p$ ranges from $0$ to $2^K - 1$.

$p$ is generated as follows: For each possible combination of trap states, consider all $K$ types of traps. Let 1 represent that a trap is harmful, and 0 represent that a trap is harmless. Treat "A" as the 0-th bit of a binary number (counting from the right), "B" as the 1st bit, "C" as the 2nd bit, and so on. Through this operation, we can obtain a $K$-bit binary number. After converting it to decimal, the $2^K$ combinations of trap states will correspond one-to-one with integers from $0$ to $2^K - 1$.

Define $s$ as the sum of all elements in $p$, i.e.: $$s = \sum_{i=0}^{2^K-1} p_i$$

Then the probability of trap state combination $i$ occurring is $p_i / s$. A valid array $p$ corresponding to the table above is: $p_0 = 36$ $p_1 = 24$ $p_2 = 24$ $p_3 = 16$

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

The player-controlled character starts with $H$ health points. When the character steps on a trap, if the trap is harmful, the character loses 1 health point; otherwise, the trap is harmless, and no health is lost. Regardless of which situation occurs, the player immediately gains information about this trap (harmful or harmless). Once health is less than or equal to 0, the character immediately dies.

The maze can be viewed as an $m \times n$ grid map, where each element can be: ".": represents flat ground, which can be passed through; "#": represents a wall, which cannot be passed through; "A", "B", "C", ...: represents a trap; "$": represents the starting point, there is exactly one in the map; "@": represents an exit, there can be multiple or none in the map.

The character can move in four directions: up, down, left, and right. Diagonal movement is not allowed, and the character cannot move outside the map.

Given the $m \times n$ map, $K$, $H$, and the probability array of size $2^K$, your task is to find the probability that the character can survive and exit the maze when executing the optimal strategy.

Input

The first line contains 4 integers, representing $m$, $n$, $K$, and $H$ respectively; The following $m$ lines each contain $n$ characters describing the maze map; The last line contains $2^K$ non-negative integers describing the array $p$, with array indices starting from 0.

Output

Contains only one number, representing the probability that the character survives and exits the maze when executing the optimal strategy. Round to 3 decimal places.

Examples

Input 1

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

Output 1

0.600

Note 1

Moving to the right, the probability that "B" is a harmful trap is $(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 a harmless trap and continues past another "B" to reach the exit, with a winning probability of 0.6.

Input 2

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

Output 2

0.800

Note 2

Moving to the left, the probability that "A" is a harmful trap is $(30 + 20)/(30 + 30 + 20 + 20) = 0.5$. If "A" is a harmful trap, 1 health point is lost, and the player turns to the right to try "B". To successfully reach the exit, "B" must be a harmless trap. Given that "A" is a harmful trap, the probability that "B" is a harmless trap is $30/(30 + 20) = 0.6$, so the probability of this scenario occurring is $0.5 * 0.6 = 0.3$. If "A" is a harmless trap, the player can control the character to pass through two "A"s in a row to reach the exit; the probability of this scenario is 0.5. Therefore, the answer is $0.3 + 0.5 = 0.8$.

Input 3

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

Output 3

1.000

Note 3

The player-controlled character has 3 health points, but at most only needs to pass through two traps, so choosing either the left or right path will allow the character to reach the exit.

Input 4

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

Output 4

0.858

Constraints

For 100% of the data, $0 \le p_i \le 10^5$, and at least one $p_i > 0$.