Domino daşları ilə döşəmə

Verilmiş oyun sahəsi $n\times m$ ölçüsündədir və bəzi hüceyrələr artıq örtülmüşdür. Boş hüceyrələri $1\times 2$ ölçüsündə domino ilə örtmək $a$ şərti vahidə başa gəlir. Sahənin boş hüceyrəsini $1\times 1$ ölçüsündə kvadrat ilə örtmək isə $b$ şərti vahidə başa gəlir.

Bütün sahəni örtmək üçün lazım olan minimum məbləği tapın.

Giriş verilənləri

Birinci sətir dörd ədəd $n,m,a,b(1\le n,m\le 100,a,b$ — modulu 1000-dən çox olmayan tam ədədlər) ehtiva edir. Növbəti $n$ sətirin hər biri $m$ simvol ehtiva edir: "." (nöqtə) simvolu sahənin örtülmüş hüceyrəsini, "*" (ulduz) simvolu isə boş hüceyrəni göstərir.

Çıxış verilənləri

Sahənin boş hüceyrələrini (və yalnız onları) örtmək üçün lazım olan minimum məbləği çıxarın.

Nümunələr