NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem1--错落有致 [alter]

1: 错落有致 [alter]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 27  Solved: 14
[Submit] [Status] [Web Board] [Creator:]

Description

在一个狭长的房间里有 N 盏吊灯,它们笔直的排成了一排。小可可是个调皮的家伙,这天他来到了这个房间,并且找到了每盏灯的开关。“为什么这些灯这么不具有美感呢?”小可可想。终于,他发现,罪魁祸首是这些灯的开关状态不够错落有致,常常连续一大片是亮的,或者连续一大片是暗的。但是小可可的时间有限,对于所有的灯,总共只能拨动不超过 K 次开关(拨动一次开关后,该灯原先灯亮会变成灯灭,原先灯灭会变成灯亮)。于是他把这些灯中,最长的连续全亮或者连续不亮的灯数量记为这些灯的不优美度,现在他想知道,通过拨动不超过 K 次开关后,他能让不优美度降到多少?



Input

第一行两个整数 N、K;

第二行一个长度为 N 的、由“N”和“F”组成的字符串,依次表示这个房间的灯光状态,

第 i 个字符为“N”表示第 i 盏灯亮,为“F”表示第 i 盏灯灭。这是一个输入格式描述信息。

Output

一行一个整数,表示最小化的不优美度。

Sample Input Copy

8 1
NNNFFNNN

Sample Output Copy

3

HINT

对于 30%的数据:1 ≤ K ≤ N ≤ 20;

对于 50%的数据:1 ≤ K ≤ N ≤ 300;

对于额外 15%的数据:1 ≤ N ≤ 100000,字符串为全 N 或全 F;

对于 100%的数据:1 ≤ K ≤ N ≤ 100000。

Source/Category