In a certain peaceful forest, there live a Fox and a Wolf. Due to common misconception, one might suppose that the Wolf would want to hunt the Fox – however, both are in fact nice animals, and get along just fine. Indeed, they have such nice manners that, if they ever meet up, they will have a nice little chat for $C$ minutes ($1 \leq C \leq 9$).

The forest that the Fox and the Wolf live in can be regarded as a rectangle, $N$ km long along its East side and $M$ km wide along its North side ($1 \leq N,M \leq 20$). It is divided into a grid of squares, each with a side length of 1 km. Each such square either contains a meadow (represented by a ‘.’), is full of burrs (‘B’), is blocked by trees (‘T’), contains the Fox’s den (‘F’), contains the Wolf’s lair (‘W’), currently contains the Fox (‘f’), or currently contains the Wolf (‘w’).

At the end of a long day at work (consisting of solving complex computer science problems in their heads), both animals wish to get to their respective homes as soon as possible. Every minute, each of them can walk one km directly North, East, South, or West, or just stay put – however, they cannot enter squares blocked by trees, nor can they enter each other’s homes (that wouldn’t be very polite). They also don’t want to leave the forest, seeing as humans jealous of their supreme intellect are constantly lurking just outside.

Every time the Fox or the Wolf goes from a square full of burrs to a meadow, he must stand still and spend $B$ minutes ($1 \leq B \leq 9$) picking burrs off of himself. As mentioned above, they must also stop and chat if they meet up. Though each square is quite big, the animals always walk to its exact centre before moving on. This means that they will meet up if they either occupy the same square at the same time, or if they pass each other while walking between squares (which would happen if they switched positions in the space of a minute). Once the animals have chatted once, they never have to chat again, having already satisfied the demands of etiquette. Both animals are great multitaskers, and can pick burrs while chatting with each other.

Each animal wants to get home as soon as possible, but is also considerate of the other – as such, they will collaborate so as to minimize the time for both of them to get home. Due to their extreme intelligence, both animals will calculate this minimum time in their heads instantly – however you, the observer, will probably need to write a program to figure it out...

Input

Line $1$: 4 integers, $N$, $M$, $C$, and $B$

Next $N$ lines: $M$ characters each, representing a row of the forest as described above

Output

A single integer – the minimum time for both the Fox and the Wolf to get to their respective homes, in minutes. If this is impossible, output -1 instead.

Example

Input:

5 6 5 1
......
BWTTTB
B.TB..
BBT..T
.FTfw.

Output:

17

Explanation of Sample:

The Wolf should wait for the first three minutes, letting the Fox go first. From then on, the Fox can continue along its only possible route home. The Wolf will be 2 squares behind the Fox most of the time, except for when it enters the burr-filled square, when it will temporarily be 1 behind. With this strategy, the Wolf will take 14 minutes to get home, while the Fox will take 17, and since we only care about the larger, the total time is 17 minutes.