配点 : 100 点
問題文
由进行花卉销售的 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是
入力
输入是按以下格式从标准输入给出的。
N K S_1 S_2 \vdots S_N
出力
答案 请打印除以 1 行输出。
入力例 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 给第几棵树施加生长剂,
- 2 第几天:BBBRGB
- 3 第几天:BBBRGB
- 4 给第几棵树施加生长剂,
第几天:GGGRGB