AT_pakencamp_2020_day2_b Walking

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_b パ研町は，南北に $ H+1 $ ブロック，東西に $ W+1 $ ブロックのグリッド状になっている． 北から $ i $ 行目，西から $ j $ 列目のブロックを$ (i,j) $ で表す． $ (1,1) $ に住んでいる Miyuki 君は，ある日散歩をしようと思い立った． 彼は $ (i,j)\ (1\ \leq\ i\ \leq\ H,1\ \leq\ j\ \leq\ W) $ に `E` または `S` の文字 $ C_{ij} $ を書き， $ (1,1) $ から開始して次のようなルールに従って散歩を行うことにした． 現在 $ (x,y) $ にいる時， - $ x\ \leq\ H $ かつ $ y\ \leq\ W $ の場合，$ C_{xy}\ = $ `E` なら東に進み，$ C_{xy}= $ `S` なら南に進む． - $ x\ =\ H+1 $ または $ y=W+1 $ の場合，散歩を終了する． この計画を知った $ (H,W+1) $ に住む Kaguya さんは，彼に散歩が終わったついでで訪問して欲しいと考え，ブロックに書かれた文字をいくつか書き換える事にした． 具体的には，`E` と書かれていた場合は `S` に，`S` と書かれていた場合は `E` に書き換える． Miyuki 君の散歩が $ (H,W+1) $ で終了するようにするためには，最少でいくつの文字を書き換える必要があるか？

入力は以下の形式で標準入力から与えられる。 > $ H\ W $ $ C_{11}\ \ldots\ C_{1W} $ $ \vdots $ $ C_{H1}\ \ldots\ C_{HW} $

標準出力に答えを出力せよ．

### 制約 - 入力は全て整数である． - $ 1\ \leq\ H,W\ \leq\ 2000 $ - $ C_{ij} $は `E` または `S` ### 小課題 1. ($ 5 $ 点) $ H=1,W=1 $ 2. ($ 15 $ 点) $ H=1 $ 3. ($ 80 $ 点) $ H=2 $ 4. ($ 200 $ 点) 追加の制約はない． ### Sample Explanation 1 このままだと散歩は $ (2,1) $ で終わってしまうため，$ (1,1) $ に書かれた文字を `E` にする． この入力は小課題 1, 2 の制約を満たす． ### Sample Explanation 2 $ (1,2) $ に書かれた文字を `E` にする事で達成できる． この入力は小課題 2 の制約を満たす． ### Sample Explanation 3 $ (1,3)\ ,\ (2,3) $ に書かれた文字をそれぞれ書き換える事で達成できる． この入力は小課題 3 の制約を満たす． ### Sample Explanation 4 この入力は小課題 4 の制約を満たす．