Problem B
Klippa protein

Din kompis Björn har nyligen påbörjat ett stort kemiexperiment, med målet att skapa ett hemligt protein. Alla protein beskrivs med strängar av bokstäver från a-z, exempelvis bcaa och hejsan. Han behöver skapa ett flertal så kallade rena proteiner. Dessa är proteiner som består av kopior av en och samma bokstav. För att göra detta har han mikroskopiska saxar som kallas CRISPR. Med hjälp av dessa kan han ta bort upp till $K$ bokstäver som ligger bredvid varandra. Med andra ord kan han välja ett intervall med upp till $K$ bokstäver att klippa bort. Om ett protein delas i två delar när det klipps kommer dessa delar sedan att sättas ihop där de klipptes av.

Eftersom han är väldigt lat vill han ha din hjälp att skriva ett program som beräknar det minsta antalet gånger han behöver klippa ett visst protein för att det ska bli rent. Notera att proteinet inte får bli en tom sträng, eftersom det isåfall inte längre kan användas för kemi.

Indata

Den första raden innehåller en sträng $P$ ($1 \leq |P| \leq 50$), proteinet Björn vill göra rent. $P$ består endast av bokstäver från a-z.

På nästa rad följer ett heltal $K$ ($1 \leq K \leq |P|$), antalet bokstäver Björn kan ta bort med en klippning.

Utdata

Skriv ut ett heltal: det minsta antalet klippningar Björn behöver göra för att proteinet ska bli rent.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

Exempelfall $1$: ett möjligt sätt är att först klippa bort bokstäverna pe. Vi får då strängen exemlfall.
Sedan kan vi klippa bort fa och får exemlll.
Till sist klippa vi bort exem och får lll, ett rent protein.

exempelfall
4

3

aabbabbba
3

2