Codeforces Round 746 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

greedy

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
F1. Alice and Recoloring 1

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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 $$$2$$$ 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 $$$3$$$ 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

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

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

Examples

Input

3 3 WWW WBB WBB

Output

3

Input

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

Output

74

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 $$$3$$$ coins.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/15/2024 06:04:00 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|