Hovuz tikintisi#4013
Siz Üzgüçülük Hovuzlarının Tikintisi üzrə Beynəlxalq Şirkətdə çalışırsınız, üzgüçülük hovuzlarının tikintisi üzrə ixtisaslaşmış bir tikinti şirkəti. Yeni bir müştəri bir neçə yeni hovuz sahəsi tikmək istəyir.
Hovuz sahəsi, sıfır və ya daha çox (mümkün disconnect edilmiş) hovuzlardan ibarət olan w×h kvadrat yamalarından ibarət düzbucaqlı bir şəbəkədir. Hovuz, daha sonra su ilə doldurulacaq bir və ya bir neçə bağlı çuxur yamalarından ibarətdir. Əvvəlcə, hər bir yamanın ya torpaqda bir çuxur ('.') ya da düz ot ('#') olduğu bir torpaq parçası ilə başlayırsınız. Bu torpaq sahəsini hovuz sahəsinə çevirmək üçün aşağıdakı qaydalara riayət etməlisiniz:
Bir yamayı olduğu kimi buraxa bilərsiniz. Bu heç bir xərc tələb etmir.
Əgər yamada əvvəlcə ot varsa, orada bir çuxur qaza bilərsiniz. Bu d EUR-a başa gəlir.
Əgər yamada əvvəlcə çuxur varsa, çuxuru doldurub üstünə ot qoya bilərsiniz. Bu f EUR-a başa gəlir.
Su hovuzdan sızmasın deyə, son ot yamaları ilə son çuxur yamaları arasında yerləşən hər bir kənar boyunca xüsusi sərhəd elementləri yerləşdirməlisiniz. Bu hər sərhəd elementi üçün b EUR-a başa gəlir.
Hovuz sahəsinin ən kənar sətirləri və sütunları həmişə ot olmalıdır.
Mövcud torpaq sahəsinin planını nəzərə alaraq mümkün olan ən ucuz hovuz sahəsinin xərcini hesablamaq tapşırığı sizə verilib.
Birinci sətirdə müsbət bir tam ədəd: test halların sayı, ən çox 100. Bundan sonra hər test halı üçün:
bir sətirdə iki tam ədəd w və h (2 ≤ w, h ≤ 50): tikinti sahəsinin eni və hündürlüyü.
bir sətirdə üç tam ədəd d, f və b (1 ≤ d, f, b ≤ 10000): yeni çuxur qazma, mövcud çuxuru doldurma və hovuz ilə ot yamaları arasında sərhəd elementi tikmə xərcləri.
h sətir, hər biri w simvoldan ibarət, orijinal tikinti sahəsinin planını göstərir.
Hər test halı üçün:
bir sətirdə bir tam ədəd: orijinal torpaq sahəsindən mümkün olan ən ucuz hovuz sahəsinin tikinti xərci.
Nümunə 1