The city 'AjobakahD' has a lot of problems with electricity. Load shedding is a common problem here and people are quite used to it. Instead of calculating the total time the power is on, they calculate the total time the power is off. And of course the later one is always greater.

There is a small area in the city, which has not yet been enlightened with any load shedding! That means they haven’t got the electricity connection yet. Now the Power Development Board (PDB) wants to set electricity connection in that area. Since the overall power in that city is not sufficient, they have decided to build a power generator in that area and want to connect all the houses to the generator.

The area can be modeled as an 8 x 8 grid. Each cell contains one of the following characters

'.' means land

'H' means house

'G' means power generator

'W' means water

Two adjacent cells can be connected by cables and the cost is 1 thousand. Two cells are said to be adjacent if they share a side. But two adjacent cells can only be connected if none of the cells is empty. Empty means either land or water. In such case, pillars can be built in the cells and after that they can be connected. The cost of placing a pillar in a land and water cell is pl and pw thousand respectively. Remember that both the costs can be zero, because there can be sponsors who might use the pillars to advertise themselves.

Now given the modeled grid of the area, the PDB wants to find the minimum cost to connect all the houses to the power generator directly or indirectly. That’s why they seek your help, as you are one of the finest programmers in town.