Svi ljubitelji kompjuterskih igrica znaju kakvo je uživanje pobediti protivnika sa što većom razlikom. U tom pogledu mali Kosta je veliki hedonista.

On i njegovi drugari vole da se povremeno okupljaju i igraju igrice po ceo dan. Oni se podele u dva tima i igraju n partija, pri čemu se nijedna partija ne završava nerešeno. Kako bi njegov tim što bolje prošao u ukupnom ishodu, Kosta vešto smišlja razne načine računanja konačnog rezultata. Omiljena strategija mu je sledeća: on n partija koje su odigrali podeli u najviše k intervala, tako da svaki interval čine uzastopne partije i svaka partija pripada tačno jednom intervalu. Za svaki interval potom računa pobednika tako što gleda čiji tim je pobedio više puta u partijama tog intervala (ako su timovi imali isto pobeda onda interval nema pobednika). Konačan rezultat Kosta onda iskazuje pobedama u intervalima, a ne u partijama.

Vaš zadatak je da pomognete Kosti da napravi takvu podelu partija na intervale da njegov tim napravi što veću razliku (po njegovom računanju), pri čemu mu je protivnički tim zadao ograničenje da ne bude više od k intervala.

Ako mu pomognete, Kosta će vas nagraditi besplatnom ulaznicom za sve utakmice američkog fudbala koje se održavaju na pomoćnom terenu iza stadiona.

Ulaz:

(Ulazni podaci se nalaze u datoteci lanparty.in) U prvom redu ulazne datoteke nalaze se prirodni brojevi n i k, razdvojeni razmakom. U narednom redu se nalazi niz od n slova pri čemu je svako od slova 'W' ili 'L'. Između tih slova nema razmaka. Slovo na i-toj poziciji označava ishod i-te partije: 'W' ako je pobedio Kostin tim, a 'L' ako je pobedio protivnički tim.

Izlaz:

(Izlazne podatke upisati u datoteku lanparty.out) Na izlaz zapišite maksimalnu razliku koju Kostin tim može ostvariti podelom partija na intervale.

Ograničenja:

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ n
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

11 5
LLWWLWLWLWW

2

Objašnjenje:

Jedan od mogućih načina da se ostvari razlika 2 je da se formira sledećih 5 intervala:

• interval 1 čine partije 1 i 2 - pobednik u ovom intervalu je protivnički tim
• interval 2 čine partije 3, 4 i 5 - pobednik u ovom intervalu je Kostin tim
• interval 3 čini samo partija 6 - pobednik je opet Kostin tim
• interval 4 čine partije 7 i 8 - oba tima imaju jednako pobeda u partijama, pa ovaj interval nema pobednika
• interval 5 čine partije 9, 10 i 11 - pobednik i u ovom intervalu je Kostin tim

Primer 2:

13 5
LLLWLLLWLLWLL

-1

Objašnjenje:

Vodite računa da najveća razlika može da bude i negativna.

const
  fin = 'lanparty.in';
  fout = 'lanparty.out';
  maxN = 100;

var
  n, k : Integer;
  res : Integer;

  (* win[i] = Da li je Kostin tim pobedio i-tu partiju *)
  win : array[1..maxN] of Boolean;

  (*
    s[m, j] = Maksimalna razlika koja se moze ostvariti ako se prvih m
    partija podele u tacno j intervala, pri cemu intervali mogu biti i
    prazni.
  *)
  s : array[0..maxN, 0..maxN] of Integer;

  (*
    w[i, r] = Rezultat intervala koji pocinje i-tom partijom i sadrzi r
    uzastopnih partija. 1 ako pobedjuje Kostin tim, -1 ako pobedjuje
    protivnicki tim, 0 ako je nereseno.
  *)
  w : array[1..maxN, 0..maxN] of Integer;



  procedure ReadInput();
  var
    f : Text;
    i : Integer;
    ch : Char;
  begin
    Assign(f, fin);
    Reset(f);

    Readln(f, n, k);
    for i := 1 to n do
    begin
      Read(f, ch);
      win[i] := ch = 'W';
    end;

    Close(f);
  end;


  procedure WriteOutput();
  var
    f : Text;
  begin
    Assign(f, fout);
    Rewrite(f);
    Writeln(f, res);
    Close(f);
  end;


  procedure Solve();
  var
    m, i, j, l, r, t : Integer;
  begin
    for i := 1 to n do
      for r := 0 to n-i+1 do
      begin
        w[i, r] := 0;
        for l := i to i+r-1 do      (* Najpre u w[i, r] pamtimo razliku u tom intervalu. *)
          if win[l] then
            inc(w[i, r])
          else
            dec(w[i, r]);

        if w[i, r] > 0 then w[i, r] :=  1;   (* Potom korigujemo tako da w[i, r] moze da *)
        if w[i, r] < 0 then w[i, r] := -1;   (* bude samo neka od vrednosti 1, 0 ili -1. *)
      end;


    for l := 0 to k do
      s[0, l] := 0;      (* Ako nije odigrana ni jedna partija razlika u intervalima je 0. *)

    for m := 1 to n do
      s[m, 0] := -10000; (* Nije moguce podeliti vise od 0 partija na 0 intervala. *)

    for j := 1 to k do
      for m := 1 to n do
      begin
        s[m, j] := -1;     (* Najgora razlika u intervalima ne moze da bude manja od -1. *)
        for r := 0 to m do (* Poslednji interval sadrzi r partija. *)
        begin
          t := s[m-r, j-1] + w[m-r+1, r];
          if t > s[m, j] then
            s[m, j] := t;
        end;
      end;


    res := s[n, k];
  end;


begin
  ReadInput();
  Solve();
  WriteOutput();
end.