Alice and Recoloring 2

给定一个 $n$ 行 $m$ 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。 现在你可以矩阵实施以下操作： 使用一块钱，选定一个包含 $(1,1)$ 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。 使用三块钱，选定一个包含 $(n,1)$ 的子矩阵，把矩阵中的元素全部反转。 使用四块钱，选定一个包含 $(1,m)$ 的子矩阵，把矩阵中的元素全部反转。 使用两块钱，选定一个包含 $(n,m)$ 的子矩阵，把矩阵中的元素全部反转。 现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。 ## 输入格式 第一行两个正整数 $n$ 和 $m (1 \le n,m\le 500)$ ，意义如上文所述。 接下来 $n$ 行，每行 $m$ 个字符 W 或 B 。意义如上文所述。 ## 输出格式 一行一个整数，表示把初始矩阵变为目标矩阵所需的最少钱数。

The difference between the versions is in the costs of operations. Solution for one version won't work for another! Alice has a grid of size $ n \times m $ , initially all its cells are colored white. The cell on the intersection of $ i $ -th row and $ j $ -th column is denoted as $ (i, j) $ . Alice can do the following operations with this grid: - Choose any subrectangle containing cell $ (1, 1) $ , and flip the colors of all its cells. (Flipping means changing its color from white to black or from black to white). This operation costs $ 1 $ coin. - Choose any subrectangle containing cell $ (n, 1) $ , and flip the colors of all its cells. This operation costs $ 3 $ coins. - Choose any subrectangle containing cell $ (1, m) $ , and flip the colors of all its cells. This operation costs $ 4 $ coins. - Choose any subrectangle containing cell $ (n, m) $ , and flip the colors of all its cells. This operation costs $ 2 $ coins. As a reminder, subrectangle is a set of all cells $ (x, y) $ with $ x_1 \le x \le x_2 $ , $ y_1 \le y \le y_2 $ for some $ 1 \le x_1 \le x_2 \le n $ , $ 1 \le y_1 \le y_2 \le m $ . Alice wants to obtain her favorite coloring with these operations. What's the smallest number of coins that she would have to spend? It can be shown that it's always possible to transform the initial grid into any other.

The first line of the input contains $ 2 $ integers $ n, m $ ( $ 1 \le n, m \le 500 $ ) — the dimensions of the grid. The $ i $ -th of the next $ n $ lines contains a string $ s_i $ of length $ m $ , consisting of letters W and B. The $ j $ -th character of string $ s_i $ is W if the cell $ (i, j) $ is colored white in the favorite coloring of Alice, and B if it's colored black.

Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.

3 3
WWW
WBB
WBB

2

10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW

68

In the first sample, it's optimal to just apply the fourth operation once to the rectangle containing cells $ (2, 2), (2, 3), (3, 2), (3, 3) $ . This would cost $ 2 $ coins.