O qədər də kobud deyil!

T'Çalla, bir çox macəradan sonra Killmonger ilə son döyüşə hazırlaşır! Filmdə qəhrəmanlar çox yorulduqları üçün münasibətlərini daha sakit bir intellektual yarışma ilə aydınlaşdırmağa qərar verdilər.

Yarışmanın qaydaları belədir: əvvəlcə Killmonger $s_1{s}_2\dots s_n$ sətrini düşünür, bu sətir $n$ kiçik latın hərflərindən ibarətdir.

Sətir $t_1{t}_2\dots t_k$-nın kobudluğu $(i,j)$ tam ədədlər cütlərinin sayıdır, burada $1\le i<j\le k$, belə ki, $t_i=$ «a», həmçinin $t_j=$ «b». Başqa sözlə, sətirin kobudluğu, bütün simvolları iki latın hərfi «a» və «b» (məhz bu ardıcıllıqla) olan sətir qalacaq şəkildə, silməyin yollarının sayıdır.

Killmonger sətri düşündükdən sonra, T'Çalla onun bəzi boş olmayan alt sətrini $s_l{s}_{l+1}\dots s_r$ seçməlidir. Bu zaman seçilmiş alt sətirin kobudluğu $c$ ədədini keçməməlidir, əks halda belə kobudluq üçün T'Çalla oyunda texniki məğlubiyyət alacaq.

T'Çalla oyunu qazanır, əgər sətirin kobudluğu $c$-dən çox olmayan bütün mümkün alt sətirlər arasında, o, uzunluğu maksimum olanını seçərsə (əgər axtarılan maksimum uzunluqda bir neçə sətir varsa, onlardan hər hansı birini). T'Çalla sizdən axtarılan alt sətiri tapmaqda kömək etməyinizi istəmir, çünki o, bu məsələni özü həll edə bilər, lakin özünü yoxlamaq üçün sizdən axtarılan alt sətirin maksimum mümkün uzunluğunu öyrənməyinizi xahiş edir.

Giriş verilənləri

Giriş məlumatlarının birinci sətri Killmonger tərəfindən düşünülmüş sətirin uzunluğunu və seçilmiş alt sətirin maksimum icazə verilən kobudluğunu göstərən iki tam ədəd $n$ və $c$-ni ehtiva edir ($1\le n\le 10^6$, $0\le c\le 10^{18}$).

İkinci sətirdə Killmonger tərəfindən düşünülmüş sətir $s$ yazılmışdır. Sətir $n$ kiçik latın hərflərindən ibarətdir.

Çıxış verilənləri

Tək bir ədəd çıxarın — düşünülmüş sətirin kobudluğu $c$-dən çox olmayan alt sətirinin maksimum uzunluğunu.

Nümunələr

Qiymətləndirmə

Bu məsələ altı alt məsələdən ibarətdir. Alt məsələlər üçün aşağıda göstərilən əlavə məhdudiyyətlər yerinə yetirilir. Alt məsələyə görə xal almaq üçün həmin alt məsələnin bütün testlərini, həmçinin əvvəlki bütün alt məsələlərin bütün testlərini keçmək lazımdır.

1. ($6$ xal): $n\le 3$;

2. ($12$ xal): $n\le 50$;

3. ($18$ xal): $n\le 700$;

4. ($18$ xal): $n\le 5000$;

5. ($24$ xal): $n\le 10^5$;

6. ($22$ xal): tam məhdudiyyətlər.