/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
パ研町は，南北に 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) で終了するようにするためには，最少でいくつの文字を書き換える必要があるか？
制約
- 入力は全て整数である．
- 1 \leq H,W \leq 2000
- C_{ij}は
EまたはS
小課題
- (5 点) H=1,W=1
- (15 点) H=1
- (80 点) H=2
- (200 点) 追加の制約はない．
入力
入力は以下の形式で標準入力から与えられる。
H \ \ W
C_{11} \ldots C_{1W}
\vdots
C_{H1} \ldots C_{HW}
出力
標準出力に答えを出力せよ．
入力例 1
1 1 S
出力例 1
1
このままだと散歩は (2,1) で終わってしまうため，(1,1) に書かれた文字を E にする．
この入力は小課題 1, 2 の制約を満たす．
入力例 2
1 2 ES
出力例 2
1
(1,2) に書かれた文字を E にする事で達成できる．
この入力は小課題 2 の制約を満たす．
入力例 3
2 3 EEE SSS
出力例 3
2
(1,3) , (2,3) に書かれた文字をそれぞれ書き換える事で達成できる．
この入力は小課題 3 の制約を満たす．
入力例 4
10 10 SEESESESES EEESESEEES EESESEESES EESSSSESES SEESSEEEEE EESESEEESS EEEESSEEEE SESESESSES SEESSEESSE EESSSSSESS
出力例 4
3
この入力は小課題 4 の制約を満たす．
Writer : define