Тэмдэгт мөрийн үзэсгэлэн гоо

256MB

933

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

Оролтын формат

Эхний мөрөнд тэмдэгт мөрийн урт болон өөрчилж болох тэмдэгтийн хамгийн их тоо болох 2 бүхэл тоо $n$ болон $k$ өгөгдөнө. 2-дахь мөрөнд зөвхөн ' $a$ ' болон ' $b$ ' үсгүүдээс тогтох тэмдэгт мөр өгөгдөнө.

Гаралтын формат

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

Хязгаарлалт

$1 \le n \le 100 000, 0 \le k \le n$

Жишээ

Оролт1

4 2
abba

Гаралт1

Оролт2

8 1
aabaabaa

Гаралт2

0.1 / 64 KiB

Редактор уншиж байна...