Mã vạch

Cho một bức ảnh gồm $n\times m$ điểm ảnh, mỗi điểm ảnh có màu trắng hoặc đen.

Bạn cần đổi màu một số điểm ảnh (càng ít càng tốt) để bức ảnh trở thành một mã vạch. Bức ảnh là mã vạch nếu thỏa mãn đồng thời hai điều kiện:

• Mọi điểm ảnh trong cùng một cột có cùng màu.
• Nếu gộp các cột liên tiếp có cùng màu thành từng nhóm, thì mỗi nhóm phải có độ rộng ít nhất $x$ cột và nhiều nhất $y$ cột.

Hãy tìm số điểm ảnh ít nhất cần đổi màu. Dữ liệu đảm bảo luôn tồn tại đáp án.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $x$, $y$.
• $n$ dòng tiếp theo, mỗi dòng gồm đúng $m$ ký tự mô tả bức ảnh ban đầu: ký tự . là điểm ảnh trắng, ký tự # là điểm ảnh đen.

Dữ liệu ra

Một số nguyên duy nhất: số điểm ảnh ít nhất cần đổi màu.

Ràng buộc

• $1\le n,m,x,y\le 1000$
• $x\le y$

Ví dụ