Description

Leader LHX is coming to City X to guide OI studies. To welcome the Leader (jiaozhu), along a road, a group of Orzer wearing T-shirts stand on both sides of the road, with big characters printed on each shirt. On one side, the Orzer spell out “欢迎欢迎欢迎欢迎……” in order, but the leader of the group suddenly notices that the Orzer on the other side, who wear the characters “教” and “主,” look less harmonious.

To describe this disharmony simply, we use j to replace “教” and z to replace “主.” A sequence composed of j and z then describes the current lineup. To make it as pleasing as possible for the Leader, you must adjust the lineup to maximize the number of jz substrings. In each adjustment, you can swap any two people at any positions, that is, swap the two letters at any positions in the sequence. Since the Leader is arriving soon, there is time for at most $K$ adjustments (you may also perform fewer than $K$), so this problem is assigned to you.

Input Format

The first line contains two positive integers $N, K$, denoting the length of the sequence and the maximum number of swaps.

The second line contains a string of length $N$, consisting only of the letters j and z, describing the sequence.

Output Format

Output a non-negative integer: after at most $K$ swaps, the maximum possible number of jz substrings.

5 2 
zzzjj

2

Hint

【Sample Explanation】

First, swap the z at position 1 with the j at position 4 to get jzzzj. Second, swap the z at position 4 with the j at position 5 to get jzzjz.

The final string has $2$ jz substrings.

【Constraints】

For $10 \%$ of the testdata, $N \le 10$.
For $30 \%$ of the testdata, $K \le 10$.
For $40 \%$ of the testdata, $N \le 50$.
For $100 \%$ of the testdata, $1 \le N \le 500$, $1 \le K \le 100$.

Translated by ChatGPT 5