Sərhədlərin dəyişdirilməsi

Bovino şəhəri Bovinoqrad rayonlarını yenidən təşkil edir! Burada yaşayan iki əsas inək cinsi - holştin və gernsiy - arasında həmişə mübahisəli siyasi proseslər baş verir, çünki hər iki cins Bovinoqrad hökumətində əhəmiyyətli təsirə malik olmaq istəyir.

Böyük metropoliten ərazi Bovinoqrad n otlaqdan ibarətdir və hər bir otlaqda bir inək var, bu inək ya holştin, ya da gernsiydir.

Bovinoqrad hökuməti bu böyük metropoliten ərazini bəzi bitişik rayonlara bölmək istəyir ki, hər bir rayon maksimum k otlaqdan ibarət olsun və hər bir otlaq yalnız bir rayona aid olsun. Hal-hazırda hökumət holştinlər tərəfindən idarə olunduğundan, onlar gernsiylərin əksəriyyət təşkil etdiyi və ya bərabər sayda olduğu rayonların sayını minimuma endirən bir yenidən bölüşdürmə üsulu tapmaq istəyirlər (rayon bərabər hesab olunur, əgər gernsiylərin sayı holştinlərin sayına bərabərdirsə).

Gernsiylərin narahat koalisiyası hökumətin rayonların yenidən bölüşdürülməsi ilə hansı zərərin vurula biləcəyini öyrənməyə çalışır. Onlara ya gernsiylərin əksəriyyət təşkil edəcəyi, ya da bərabər rayonların olacağı ən pis minimal rayon sayını müəyyən etməyə kömək edin.

Giriş Məlumatları

Birinci sətir iki tam ədəd n (1 ≤ n ≤ 3 * 10^5) və k (1 ≤ k ≤ n) ehtiva edir. İkinci sətir uzunluğu n olan bir sətir ehtiva edir. Hər bir simvol holştin və ya gernsiy inəyi üçün 'H' və ya 'G' dir.

Çıxış Məlumatları

Gernsiylərin əksəriyyət təşkil edəcəyi və ya bərabər rayonların olacağı minimal mümkün rayon sayını çıxarın.