Problem description

Ola wymyśliła sobie wzór, który chciałaby pomalować na ścianie. Jest on prostokątem, który składa się z małych kwadracików i ma wymiary H × W.

Pomalowanie pola o współrzędnych (i,j) zajmuje jej C_i, j sekund – ta liczba zależy od porowatości ściany i wielu innych czynników, na których nie chcemy się skupiać. Na szczęście nie musi ona malować każdego kwadracika osobno, bo jeśli sąsiednie kwadraciki są jednego koloru i tworzą pas, to może być szybciej pomalować cały pasek jednym pociągnięciem pędzla. Formalnie, Ola może może pomalować pionowy pasek grubości jednostkowej (a dowolnej długości) w A sekund, ewentualnie poziomy pasek grubości jednostkowej (a dowolnej długości) w B sekund – oczywiście malowane pasy muszą składać się z pól o tym samym kolorze. Na szczęście, można wiele razy malować jedno pole, więc Ola może każde pole pomalować pionowo, poziomo i nawet dla pewności indywidualnie – ważne, by było pomalowane przynajmniej raz (ale za każdym razem na ten sam kolor, bo inaczej stare warstwy będą ,,przebijać’’ i odróżniać się kolorem).

Oczywiście, Ola chciałaby jak najszybciej pomalować swój wzór, więc powiedz jej, ile czasu musi na to przeznaczyć.

Napisz program, który: wczyta opis wzoru Oli, wyznaczy minimalny czas pomalowania tego wzoru na ścianie i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby naturalne H, W, A oraz B – odpowiednio wysokość i szerokość planszy oraz czas malowania jednego pasa pionowego i poziomego. W kolejnych H wierszach znajduje się opis wzoru, który Ola chce namalować – każda linia jest S-literowym słowem składającym się z małych liter alfabetu angielskiego. Równe litery określają równe kolory, a różne litery – różne kolory. W kolejnych H wierszach podane są czasy, ile zajmuje pomalowanie każdego z pól malując indywidualnie – j-ta z liczb w i-tym wierszu to C_i, j – czas malowania jedynie pola o współrzędnych (i,j).

Wyjście

Twój program powinien wypisać na wyjście jeden wiersz z minimalną liczbą sekund jakie Ola potrzebuje by pomalować cały swój wzór.

Ograniczenia

1 ≤ H, W ≤ 30, 1 ≤ A, B ≤ 1 000, 1 ≤ C_i, j ≤ 1 000.

Przykład

2 2 4 5
aa
bc
3 4 
2 1

8