C. Вася ба тэмдэгт мөр

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ахлах сургуулийн сурагч Вася $n$ урт бүхий тэмдэгт мөрийг төрсөн өдрийн бэлэг болгон авчээ. Уг тэмдэгт мөр нь зөвхөн '$a$' болон '$b$' гэсэн үсгүүдээс тогтдог байв. Вася уг тэмдэгт мөрийн гоо үзэсгэлэн гэдгээр уг тэмдэгт мөрийн зөвхөн ижил үсгүүдээс тогтох дэд тэмдэгт мөрийн (тасралтгүй дэд дараалал) боломжит хамгийн их уртын хэмжээг тэмдэглэжээ.

Вася анхны тэмдэгт мөрийн $k$-аас ихгүй тэмдэгтийг өөрчилж чадах байв. Тэгвэл тэрээр хэсэг тэмдэгтийг өөрчлөх замаар үүсгэж чадах тэмдэгт мөрийн хамгийн их гоо үзэсгэлэнгийн утгыг олно уу.

Оролт

Эхний мөрөнд тэмдэгт мөрийн урт болон өөрчилж болох тэмдэгтийн хамгийн их тоо болох 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 100 000, 0 ≤ k ≤ n$) өгөгдөнө.

2-дахь мөрөнд зөвхөн '$a$' болон '$b$' үсгүүдээс тогтох тэмдэгт мөр өгөгдөнө.

Гаралт

$k$-аас ихгүй тэмдэгтийг солих замаар Вася-ын үүсгэж чадах тэмдэгт мөрийн хамгийн их гоо үзэсгэлэнгийн утга болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4 2
abba
Гаралт
4
Оролт
8 1
aabaabaa
Гаралт
5

Тэмдэглэл

Эхний жишээнд Вася "$aaaa$" болон "$bbbb$" гэсэн тэмдэгт мөрүүдийг 2-ууланг нь үүсгэж чадна.

2-дахь жишээний оновчтой хариулт нь "$aaaaabaa$" эсвэл "$aabaaaaa$ гэсэн тэмдэгт мөр үүсгэх юм.

Сэтгэгдлүүдийг ачааллаж байна...