C - ロシアの旗 (Russian Flag) Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点: 100

問題

K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした.K 理事長はまず倉庫から古い旗を取り出してきた.この旗は NM 列のマス目に分けられていて,それぞれのマスには白・青・赤のいずれかの色が塗られている.

K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている.ただし,この問題でいうロシアの旗とは以下のようなものである.

  • 上から何行か(1 行以上)のマスが全て白で塗られている.
  • 続く何行か(1 行以上)のマスが全て青で塗られている.
  • それ以外の行(1 行以上)のマスが全て赤で塗られている.

K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ.


入力

入力は 1 + N 行からなる.

1 行目には,2 つの整数 N, M (3 \leqq N \leqq 503 \leqq M \leqq 50) が空白を区切りとして書かれている.これは,旗が NM 列のマス目に区切られていることを表す.

続く N 行にはそれぞれ M 文字からなる文字列が書かれており,古い旗のマス目に塗られている色の情報を表す.N 行のうちの i 行目の j 文字目 (1 \leqq i \leqq N1 \leqq j \leqq M) は,古い旗のマス目の i 行目 j 列目のマスの色を表す WBR のいずれかの文字である. W は白,B は青,R は赤を表す.

出力

K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を 1 行で出力せよ.


入力例 1

4 5
WRWRW
BWRWB
WRWRW
RWBWR

出力例 1

11

入出力例 1 において,古い旗には下図のように色が塗られている.

2016-yo-t3-fig01.png

下図において,X の書かれた 11 個のマスを塗り替える.

2016-yo-t3-fig02.png

これにより下図のようなロシアの旗にすることができる.

2016-yo-t3-fig03.png

11 個未満のマスを塗り替えることではロシアの旗にすることはできないため,11 を出力する.


入力例 2

6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW

出力例 2

44

入出力例 2 においては,古い旗には下図のように色が塗られている.

2016-yo-t3-fig04.png