Lát nền quảng trường

Quảng trường nhà hát là một hình chữ nhật kích thước $n\times m$ mét, được chia thành lưới $n$ hàng và $m$ cột ô vuông đơn vị. Ô ở hàng $i$, cột $j$ được ký hiệu là $a_{i,j}$:

• nếu $a_{i,j}$ là ký tự * thì ô đó đã được lát sẵn;
• nếu $a_{i,j}$ là ký tự . thì ô đó còn trống và bạn phải lát nó.

Có hai loại gạch để lựa chọn:

• gạch $1\times 1$, giá $x$ đồng, phủ đúng $1$ ô;
• gạch $1\times 2$, giá $y$ đồng, phủ đúng $2$ ô kề nhau trong cùng một hàng.

Gạch $1\times 2$ không được xoay (nên không thể phủ hai ô kề nhau theo chiều dọc) và không được cắt thành hai viên $1\times 1$.

Bạn phải phủ hết mọi ô trống, hai viên gạch bất kỳ không được chồng lên nhau, và không viên gạch nào được phủ lên ô đã lát sẵn.

Hãy tính tổng chi phí nhỏ nhất để lát hết các ô trống.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa bốn số nguyên $n$, $m$, $x$, $y$: kích thước quảng trường, giá viên gạch $1\times 1$ và giá viên gạch $1\times 2$.
  • $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự . hoặc * mô tả lưới.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le t\le 500$
• $1\le n\le 100$
• $1\le m\le 1000$
• $1\le x,y\le 1000$
• Tổng $n\times m$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ