1397 - jz

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 43

Solved: 7

Description


A string contains only 'j' and 'z'. You can perform the operation of swapping any two characters at most K times. What is the maximum number of appearance times of substring "jz" after at most K operations?


Input


First line contains N and K, indicating the length of string and the largest number of swapping.( 1<=N<=500, 0<=K<=100 )



Second line contains a string only contains lowercase characters 'j' and 'z'.


Output


The maximum appearance times.


sample input
5 2
zzzjj
sample output
2
hint

First step, change the string to jzzzj.

Second step, change it to jzzjz.

Finally, you'll get two substring of "jz" in jzzjz.

source
Orz教主第4次模拟赛
© 2015 HUST ACMICPC TEAM. All Right Reserved.