Ispred muzeja programerskih nauka u Nišu je velika gužva - već se napravio red od n posetilaca. Među osobama u redu ima onih koji nemaju nikakve popuste u muzeju ('b' tip osoba) i onih koji imaju 50% popusta jer su rešavali Problem Meseca ('a' tip osoba).

Laza radi kao organizator u muzeju i njegov posao je da posetioce, u redosledu dolaska, raspoređuje u grupe, gde je grupa skup nekoliko uzastopnih osoba u redu. Svaka osoba iz reda mora pripadati taqno jednoj grupi i nijedna grupa ne sme biti prazna. Takođe, zbog politike muzeja, u svakoj grupi, broj osoba tipa 'a' mora biti veći ili jednak od broja osoba tipa 'b'. Posle formiranja, jedna po jedna grupa, redom od početka reda, provodi 1 sat u obilasku muzeja dok preostale grupe čekaju.

Iako obiqno radi svoj posao vrlo savesno, Laza je zapazio da je m-ta osoba u redu zapravo član redakcije Problema Meseca koji mu jednom nije priznao zadatak i zbog toga je odlučio da sada napravi izuzetak. On želi da podeli posetioce u grupe tako da pomenuti član redakcije čeka što duže pre nego što na njegovu grupu dođe red. Pomozite mu u tome.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke muzej.in.) U prvom redu ulazne datoteke nalaze se dva prirodana broja n i m, redom, broj osoba koje čekaju u redu i pozicija pomenutog člana redakcije (1 ≤ m ≤ n ≤ 300.000). U narednom redu nalazi se string dužine n sastavljen isključivo od slova a i b - opis reda. Početak stringa je početak reda dok slova predstavljaju odgovarajuće tipove osoba. Ulazni podaci će biti takvi da će Laza uvek moći da izvrši neki raspored posetilaca u grupe.

Izlaz.

(Izlazni podaci se ispisuju u datoteku muzej.out) U prvom i jedinom redu izlazne datoteke ispisati jedan ceo broj - broj sati koje će morati da čeka m-ta osoba u redu, pri najnepovoljnijoj podeli, pre nego što dođe red na njegovu grupu.

Primer 1.

10 8
aabaabbbaa

4

Objašnjenje.Ukoliko red podelimo na 5 grupa: a | ab | a | ab | bbaa, osma osoba (podvučena je) će morati da čeka prve 4 grupe, tj. čekaće 4 sata. Ne postoji podela u kojoj osma osoba u redu čeka duže.

Napomena.
U 30% test primera je n ≤ 3.000, dok je u 60% test primera n = m, tj. član redakcije je poslednja osoba u redu.

#include <cstdlib>
#include <cstdio>

const int MaxN = 1000100;

int n, m, sol;
char s[MaxN];
int p[MaxN], d[MaxN], rightmost[MaxN];

int main()
{
  freopen("muzej.in", "r", stdin);
  freopen("muzej.out", "w", stdout);

  scanf("%d%d", &n, &m);
  scanf("%s", s);

  p[0] = 0;
  for (int i = 1; i <= n; i++)
    if (s[i - 1] == 'a') 
      p[i] = p[i - 1] + 1;
    else
      p[i] = p[i - 1] - 1;

  for (int i = 0; i <= n; i++) 
    rightmost[i] = 0;

  d[0] = 0;
  for (int i = 1; i <= n; i++)
  {
    if (p[i] >= 0)
    {
      d[i] = d[ rightmost[ p[i] ] ] + 1;
      if (p[i - 1] < p[i] && d[i - 1] + 1 > d[i])
        d[i] = d[i - 1] + 1;

      rightmost[ p[i] ] = i;
    }
    else
    {
      d[i] = -1;
    }
  }

  sol = 0;
  for (int i = 0; i < m; i++)
    if (d[i] > sol && p[n] - p[i] >= 0) sol = d[i];

  printf("%d\n", sol);
  return 0;
}

const
  MaxN = 1000100;
  
var
  inFile, outFile : text;
  n, m, sol, i : longint;
  s : array[0..MaxN] of char;
  p, d, rightmost : array[0..MaxN] of longint;

BEGIN

  assign(inFile, 'muzej.in');
  assign(outFile, 'muzej.out');
  reset(inFile); rewrite(outFile);
  
  readln(inFile, n, m);
  for i := 1 to n do
    read(inFile, s[i]);

  p[0] := 0;
  for i := 1 to n do
    if (s[i] = 'a') then
      p[i] := p[i - 1] + 1
    else
      p[i] := p[i - 1] - 1;

  for i := 0 to n do
    rightmost[i] := 0;

  d[0] := 0;
  for i := 1 to n do begin

    if (p[i] >= 0) then begin
    
      d[i] := d[ rightmost[ p[i] ] ] + 1;
      if ((p[i - 1] < p[i]) AND (d[i - 1] + 1 > d[i])) then
        d[i] := d[i - 1] + 1;

      rightmost[ p[i] ] := i;
      
    end
    else
      d[i] := -1;
  end;

  sol := 0;
  for i := 0 to m - 1 do
    if ((d[i] > sol) AND (p[n] - p[i] >= 0)) then
      sol := d[i];

  writeln(outFile, sol);
  close(inFile);
  close(outFile);

END.