Dırnaq, Kağız, Qayçı (Qızıl)
"Daş, Kağız, Qayçı" oyununu yəqin ki, eşitmisiniz. İnekler də buna bənzər bir oyun oynamağı sevirlər: "Dırnaq, Kağız, Qayçı". Bu oyunun qaydaları çox sadədir. İki inək bir-birinə qarşı oynayır. Onlar üçə qədər sayır və sonra eyni anda dırnaq, kağız və ya qayçını təmsil edən bir işarə göstərirlər. Dırnaq qayçını məğlub edir, qayçı kağızı məğlub edir, kağız isə dırnağı məğlub edir. Əgər hər iki inək eyni işarəni göstərərsə, nəticə bərabərlik olur.
Fermer Con Bessi ilə n dəfə oynamaq istəyir. Bessi bu oyunun eksperti olaraq FJ-nin hər bir işarəsini əvvəlcədən təxmin edə bilir. Lakin, inək olaraq, o çox tənbəldir. Buna görə də, o, eyni işarəni ardıcıl olaraq çox dəfə oynamaq istəyir. Əslində, o, bütün oyunlar ərzində işarələr arasında ən çox k dəfə keçid etmək istəyir. Məsələn, əgər k = 2 olarsa, o, ilk oyunlarda "dırnaq" oynaya bilər, sonra kağıza keçə bilər və sonda yenidən "dırnaq" oynaya bilər.
FJ-nin oynayacağı işarələrin ardıcıllığına görə, Bessinin qazana biləcəyi maksimum oyun sayını müəyyən edin.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və k (0 ≤ k ≤ 20) ədədlərini ehtiva edir. Qalan n sətir FJ-nin işarələrini ehtiva edir, hər biri H, P və ya S.
Çıxış məlumatları
Bessinin ən çox k dəfə keçid edə biləcəyi halda qazana biləcəyi maksimum oyun sayını çıxış edin.