問題文

花の販売を行う Universal Tropical Plant Center (UTPC) 社が所有する農園は、東西に一列に N 本の木が植えられており、西から順に 1,2,\dots,N の番号が付いています。

UTPC 社の農園ではこれから、K 日間の収穫期に入ります。収穫期の間、それぞれの木は毎日、赤、緑、青のいずれかの色の花を 1 つだけ咲かせます。木 i が今後 K 日間で咲かせる花の色の情報は文字列 S_i で表され、j 日目に咲かせる花の色について、S_i の j 文字目 S_{i,j} が R の場合は赤色、 G の場合は緑色、 B の場合は青色であることを表します。

UTPC 社では毎日、その日に咲いた全ての花を収穫し、3 つずつ花束にして販売します。この花束は必ず、3 つの花が全て同じ色か、全て異なる色になるようにします。 本来は、毎日収穫した花が 1 つも余らないように花束を作りたいのですが、現状ではこのような花束の作り方が存在するとは限りません。そこで、収穫期に入る前に、次の操作をそれぞれ好きな回数繰り返すことにしました。

• 1 以上 N 以下の整数 i を選び、木 i を切る。切った木からは花が収穫できなくなる。
• 1 以上 N 以下の整数 i を選び、木 i に促進剤をかける。促進剤をかけると、今後 K 日間は 2 つの花を咲かせるようになる。つまり、j 日目には S_{i,j} の色の花を 2 つ咲かせることになる。

なお、同じ木に対して 2 回以上操作を行うことはできません。また、この操作は収穫期に入った後に行うことはできません。

UTPC 社の事務所は農園の西端にあるので、東に植えられている木に対してはなるべく操作を行いたくないです。そこで、一連の操作のコストを、操作した木のうち最も東側にあるものの番号によって定義します。どの木に対しても操作を行わない場合のコストは 0 とします。

収穫期の間どの日も花が 1 つも余らなくなるような操作方法の中での、コストの最小値を求めてください。なお、全ての木を切った場合、花は 1 つも余らないと考えるものとします。

制約

• N, K は整数
• 1 \leq N,K
• NK \leq 10^5
• |S_i|=K
• S_i の各文字は R, G, B のいずれかである

入力例 1

4 5
RGBGR
BGGBR
RBGBR
RRRRR

出力例 1

2

2 番目の木を切ると、咲く花の色は

• 1 日目：RRR
• 2 日目：GBR
• 3 日目：BGR
• 4 日目：GBR
• 5 日目：RRR

となり、どの日も条件を満たします。この場合のコストは 2 です。コスト 1 で目標を達成することはできません。

入力例 2

3 3
RGB
BGG
GGR

出力例 2

0

操作を行う必要はありません。

入力例 3

3 4
GGGG
BGGG
GGGR

出力例 3

3

全ての木を切る必要があります。

入力例 4

6 4
BGGB
BGGB
RGBG
RRRR
GGGG
BBBB

出力例 4

3

1 番目の木に促進剤をかけ、3 番目の木を切ると、咲く花の色は

• 1 日目：BBBRGB
• 2 日目：GGGRGB
• 3 日目：GGGRGB
• 4 日目：BBBRGB

となり、どの日も条件を満たします。