Problem Description

Pakken Town is a grid of blocks with $ H+1 $ blocks from north to south and $ W+1 $ blocks from west to east. The block at the $ i $-th row from the north and the $ j $-th column from the west is represented as $ (i,j) $.
Miyuki, who lives at $ (1,1) $, decided to go for a walk one day. He wrote the characters E or S on the blocks $(i,j)\ (1 \leq i \leq H, 1 \leq j \leq W)$ and decided to follow these rules for his walk starting from $ (1,1) $:

• When at $ (x,y) $,
• If $x \leq H$ and $y \leq W$, move east if $ C_{xy} = $ E and move south if $ C_{xy} = $ S.
• If $ x = H+1 $ or $ y = W+1 $, end the walk.

Kaguya, who lives at $ (H,W+1) $, wants him to visit her after his walk. She decided to change some of the characters on the blocks: E to S and S to E.
What is the minimum number of characters that need to be changed so that Miyuki's walk ends at $ (H,W+1) $?

Input Format

The input is given from the standard input in the following format:

$H\ W$ $C_{11}\ \ldots\ C_{1W}$ $\vdots$ $C_{H1}\ \ldots\ C_{HW}$

Output Format

Output the answer to the standard output.

Sample Input and Output

Sample Input #1

1 1
S

Sample Output #1

1

Sample Input #2

1 2
ES

Sample Output #2

1

Sample Input #3

2 3
EEE
SSS

Sample Output #3

2

Sample Input #4

10 10
SEESESESES
EEESESEEES
EESESEESES
EESSSSESES
SEESSEEEEE
EESESEEESS
EEEESSEEEE
SESESESSES
SEESSEESSE
EESSSSSESS

Sample Output #4

3

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq H,W \leq 2000$
• $ C_{ij} $ is either E or S.

Subtasks

1. ($ 5 $ points) $ H=1,W=1 $
2. ($ 15 $ points) $ H=1 $
3. ($ 80 $ points) $ H=2 $
4. ($ 200 $ points) No additional constraints.

Sample Explanation 1

If left unchanged, the walk will end at $ (2,1) $, so change the character at $ (1,1) $ to E. This input satisfies the constraints of Subtasks 1 and 2.

Sample Explanation 2

Achievable by changing the character at $ (1,2) $ to E. This input satisfies the constraints of Subtask 2.

Sample Explanation 3

Achievable by changing the characters at $ (1,3) $ and $ (2,3) $ respectively. This input satisfies the constraints of Subtask 3.

Sample Explanation 4

This input satisfies the constraints of Subtask 4.

见题面 Input 部分

见题面 Output 部分