CF1592F2.Alice and Recoloring 2

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.

不同版本之间的区别在于操作的花费。一个版本的解法无法适用于另一个版本！

爱丽丝有一个大小为 $n \times m$ 的网格，初始时所有格子均为白色。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。爱丽丝可以对这个网格执行以下操作：

• 任选一个包含格子 $(1, 1)$ 的子矩形，并翻转该子矩形中所有格子的颜色（翻转指将白色变为黑色，或黑色变为白色）。
  此操作花费 $1$ 枚硬币。

• 任选一个包含格子 $(n, 1)$ 的子矩形，并翻转该子矩形中所有格子的颜色。
  此操作花费 $3$ 枚硬币。

• 任选一个包含格子 $(1, m)$ 的子矩形，并翻转该子矩形中所有格子的颜色。
  此操作花费 $4$ 枚硬币。

• 任选一个包含格子 $(n, m)$ 的子矩形，并翻转该子矩形中所有格子的颜色。
  此操作花费 $2$ 枚硬币。

需要提醒的是：子矩形是指满足 $x_1 \le x \le x_2$、$y_1 \le y \le y_2$ 的所有格子 $(x, y)$ 组成的集合，其中 $1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le m$。

爱丽丝希望借助这些操作得到她最喜爱的染色方案。她最少需要花费多少枚硬币？可以证明：从初始网格出发，总能通过若干次操作得到任意目标染色方案。

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.

输入的第一行包含两个整数 $n, m$（$1 \le n, m \le 500$）——表示网格的尺寸。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$，由字母 W 和 B 组成。字符串 $s_i$ 的第 $j$ 个字符为 W 表示 Alice 最喜欢的染色方案中单元格 $(i, j)$ 被染成白色，为 B 表示被染成黑色。

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

输出Alice为实现她最喜欢的染色方案所需花费的最少硬币数量。

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.

在第一个样例中，最优策略是仅对包含格子 $(2, 2), (2, 3), (3, 2), (3, 3)$ 的矩形应用第四种操作一次，花费为 $2$ 枚金币。