Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
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 Ci, 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 Ci, 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 ≤ Ci, j ≤ 1 000.
Przykład
| Wejście | Wyjście | |
|
|