Tô vạch

Bạn được cung cấp một bức ảnh có kích thước \(n \times m\) điểm ảnh. Mỗi điểm ảnh là màu trắng hoặc đen.

Nhiệm vụ của bạn là thay đổi càng ít điểm ảnh càng tốt để bức ảnh trở thành một mã vạch hợp lệ.

Một bức ảnh được xem là mã vạch nếu thỏa mãn hai điều kiện sau:

• Mỗi cột chỉ có một màu duy nhất (hoặc toàn trắng, hoặc toàn đen).
• Khi nhóm các cột liền kề có cùng màu lại, kích thước của mỗi nhóm phải nằm trong đoạn \([x, y]\).

Mục tiêu: Tìm số điểm ảnh ít nhất cần tô lại để bức ảnh trở thành mã vạch hợp lệ.

\InputFile

• Dòng đầu tiên chứa bốn số nguyên \(n, m, x, y\) (\(1 \le n \times m \le 10^6, x \le y \le 10^6\)).
• Tiếp theo là \(n\) dòng, mỗi dòng gồm đúng \(m\) ký tự, mô tả bức ảnh ban đầu.
• Mỗi ký tự là '.' (điểm trắng) hoặc # (điểm đen).

\OutputFile

In ra một số nguyên duy nhất --- số điểm ảnh ít nhất cần tô lại. Đảm bảo rằng luôn tồn tại cách làm thỏa mãn yêu cầu.

\Scoring

• Subtask 1 (22 điểm): \(n \cdot m \le 20\)
• Subtask 2 (18 điểm): Tất cả các ô đều có màu trắng.
• Subtask 3 (30 điểm): \(m \le 1000\)
• Subtask 4 (30 điểm): Không có giới hạn gì thêm

Example

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

11

2 5 1 1
#####
.....

5