Условие

---

А. Топки 
---
Софтуерна компания е разработила играта "Топки". Играе се от един играч на правоъгълна дъска, разделена на N x M клетки, като всяка клетка е определена с координатите си (X, Y) –  номера на реда и номера на колоната, съответно. Клетките на дъската могат да бъдат свободни, т.е. такива, в които може да се постави една топка, или блокирани. Играчът получава начална позиция с B топки върху дъската и крайната позиция с E топки, която трябва да достигне от началната, с някои от следните три операции: 
- Първата операция може да се приложи към свободна клетка, ако в нея няма топка. В резултат в клетката се появява топка, а играчът получава A наказателни точки; 
- Втората операция може да се приложи към свободна клетка с топка. В резултат топката изчезва, а играчът получава B наказателни точки; 
- Третата операция може да се приложи към двойка съседни свободни клетки, ако в първата има топка, а във втората – няма. В резултат на операцията топката се премества от първата клетка във втората, а играчът получава C наказателни точки. Две клетки (X1, Y1) и (X2, Y2) са съседни, ако |X1 – X2| + |Y1 – Y2| = 1.  
Напишете програма, която намира решение с най-малък брой наказателни точки. 

Вход. На първия ред на стандартния вход ще бъде зададен броят на тестовете, които програмата трябва да реши при едно изпълнение. Първият ред за всеки тест ще съдържа, разделени с един интервал, двете цели числа N и M – броя на редовете и броя на колоните, съответно, а вторият ред – целите A, B и C, разделени с по един интервал. Всеки от следващите N реда съдържа по M знака Si,j, с които се описва началната позиция на топките: Ако Si,j = '#', тогава клетката с координати (i, j) е блокирана.  Ако Si,j = '.', тогава клетката с координати (i, j) е свободна и не съдържа топка, а ако Si,j = '*', тогава клетката с координати (i, j) е свободна и съдържа топка. Следва един празен ред, а след него N реда с по M знака, които по подобен начин описват крайната позиция.  

Изход: За всеки тестов пример, в реда по който са зададени на входа, програмата трябва да изведе на стандартния изход ред с цялото число R такова, че най-евтиният начин за постигане на крайната позиция е с R наказателни точки.

Ограничения: 3 ≤ N, M ≤ 60, 0 ≤ A, B, C ≤ 1000 

Примерен вход:
1
5 6
4 5 2
**#...
..*.##
.*.*.*
..#.##
..#.*.
*.#..*
..*.##
**....
..#.##
**#*..

Примерен изход:
29