Đặc trưng Haar

Trong thuật toán nhận diện khuôn mặt của Viola và Jones, người ta cần tính giá trị của các đặc trưng Haar trên ảnh. Ta xét mô hình đơn giản hoá sau.

Một bức ảnh là bảng kích thước $n\times m$, mỗi ô chứa một số nguyên là độ sáng của điểm ảnh đó. Một đặc trưng cũng là bảng kích thước $n\times m$, mỗi ô được tô màu trắng (W) hoặc đen (B).

Giá trị của đặc trưng trên một bức ảnh được tính như sau: đặt đặc trưng chồng khít lên ảnh (không xoay, không lật), khi đó giá trị đặc trưng bằng $W-B$, trong đó $W$ là tổng độ sáng các điểm ảnh nằm dưới ô trắng, còn $B$ là tổng độ sáng các điểm ảnh nằm dưới ô đen.

Để tính nhanh giá trị này, người ta dùng các hình chữ nhật tiền tố: đó là hình chữ nhật bất kỳ trên ảnh có góc trên trái trùng với góc trên trái của ảnh. Ta có một biến $value$ ban đầu bằng $0$. Trong một thao tác, ta được chọn một hình chữ nhật tiền tố bất kỳ, tính tổng độ sáng các điểm ảnh trong đó, nhân với một số nguyên tuỳ ý rồi cộng vào $value$.

Cho một đặc trưng, hãy tính số thao tác ít nhất cần dùng để với mọi bức ảnh, sau khi thực hiện các thao tác đó, $value$ đúng bằng giá trị của đặc trưng trên bức ảnh.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số hàng và số cột của đặc trưng.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả đặc trưng: ký tự thứ $j$ của dòng thứ $i$ là W nếu ô đó màu trắng, là B nếu ô đó màu đen.

Dữ liệu ra

In ra một số nguyên duy nhất: số thao tác ít nhất cần thực hiện.

Ràng buộc

• $1\le n,m\le 100$

Ví dụ