Alice and Recoloring 2
Contest: Codeforces Round 746 (Div. 2)
Difficulty rating: 2800
Tags: constructive algorithms, flows, graph matchings, greedy

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.

Input format:
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 format:
Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 3
WWW
WBB
WBB

Example output:
2

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

Example output:
68

Editorial:
Everything from the editorial of the first part of the problem stays the same, except one thing: now the second operation on the modified grid costs only $$$2$$$ coins. Sadly, now it's not true that it's not optimal to use the second operation more than once.
Let's denote the second operation on $$$a$$$ by $$$op(x, y)$$$ (meaning that we invert numbers at $$$a[x][y], a[n][y], a[x][m], a[n][m]$$$). New claim is that it's not optimal to make operations which have the same $$$x$$$ or the same $$$y$$$.
Indeed, suppose that we made $$$op(x, y_1)$$$ and $$$op(x, y_2)$$$. Then cells $$$a[x][m]$$$ and $$$a[n][m]$$$ haven't changed, so we only flipped $$$4$$$ cells with cost of $$$2\times 2 = 4$$$ coins. We could have done this with operations of the first type.
Another observation: it doesn't make sense to make $$$op(x, y)$$$, unless all the cells $$$a[x][y], a[x][m], a[n][y]$$$ are $$$1$$$. Indeed, no other operation of this type will affect any of these cells. If some cell here is $$$0$$$, and we still make $$$op(x, y)$$$ in $$$2$$$ coins, then we will have to spend one additional coin on reverting it back to $$$0$$$ with the operation of the first type. Instead, you could have just flipped $$$3$$$ other cells from $$$a[x][y], a[x][m], a[n][y], a[n][m]$$$ with the operations of the first type in the same $$$3$$$ coins.
How many such operations can we make then? Let's build a bipartite graph, with parts of sizes $$$n-1$$$ and $$$m-1$$$, and connect node $$$x$$$ from the left part with node $$$y$$$ from the right part iff $$$a[x][y] = a[x][m] = a[n][y] = 1$$$. Find the maximum matching in this graph with your favorite algorithm (for example, in $$$O(mn\sqrt{m+n})$$$ with Hopcroft–Karp), let its size be $$$K$$$. Then, for each $$$0 \le k \le K$$$, we can find the number of ones that will be left in the grid if we make exactly $$$k$$$ operations of the second type. Then the answer to the problem is just the minimum of $$$(ones\_left+2k)$$$ over all $$$k$$$.