Zədələnmiş parket
Döşəmə ölçüsü M×N olan bir otaq parketlə döşənmişdir. Lakin bəzi parket plitələri zədələnmişdir. Pyotr bu otaqda təmir işləri aparmağa qərar verdi və yalnız zədələnmiş plitələri dəyişdirmək istədi. Mağazaya gəldikdə, o, parket plitələrinin iki növ olduğunu gördü: ölçüsü 1×2 olanlar A rubl (bir az düşündükdən sonra Pyotr başa düşdü ki, 1×2 ölçülü plitələri 90 dərəcə döndərərək 2×1 ölçülü plitələr əldə etmək mümkündür) və ölçüsü 1×1 olanlar B rubl. Pyotr 1×2 ölçülü plitəni 1×1 ölçülü iki plitəyə bölə bilmir.
Pyotra təmir üçün lazım olan minimum məbləği müəyyən edin.
Giriş verilənləri
Giriş faylının ilk sətiri 4 ədəd N, M, A, B (1 ≤ N, M ≤ 300, A, B – modulu 1000-dən çox olmayan tam ədədlər) ehtiva edir. Növbəti N sətirin hər biri M simvolu ehtiva edir: "." (nöqtə) simvolu zədələnməmiş parket plitəsini, "*" (ulduz) simvolu isə zədələnmiş plitəni göstərir. Sətirlərin sonunda əhəmiyyətsiz boşluqlar ola bilər. Faylın sonunda boş sətirlər ola bilər.
Çıxış verilənləri
Çıxış faylında bir ədəd yazın – zədələnmiş parketləri (və yalnız onları) dəyişdirmək üçün lazım olan minimum məbləğ.