题目描述

现在面条老师获得了一个字符串。面条老师可以将若干位置上的字符变为小写字母a。每次改变消耗一点能量。记面条老师改变过后的字符串为$S$。

S每经过一秒，其上的a会往左右两侧扩展，将旁边的字母同化成小写字母a。例如对于串bbbbabb，一秒后变成bbbaaab，两秒后变成bbaaaaa，三秒后变成baaaaaa，四秒后变成aaaaaaa。当所有字符都变成小写字母a后，称为同化完成。

要求面条老师改变后的字符串$S$的同化完成用时不超过$k$秒。你的任务是帮助面条老师计算他所消耗的最少能量值。

输入格式

第一行两个正整数$n, k$，表示字符串的长度为$n$，同化用时长度不超过$k$秒。

接下来一行一个长度为$n$的字符串，表示面条老师被给定的$n$个字符。仅包含英文小写字母。

输出格式

一行一个整数表示面条老师所需要消耗的最少能量。

10 1
abbbbabbbb

2

样例解释

其中一种符合要求的修改办法是面条老师将串变成abbababbab，该串可以在不超过1秒的情况下完成同化。

数据规模与约定

每组数据点10分，共10组数据。

对于所有数据，均有$1 \le n,k \le 200,000$

大样例

大样例下载