Given a string $S$ consisting of $n$ characters $\in$ $\\{0,1\\}$ and a natural number $k$. Find a way to modify the minimum number of characters in the string $S$ (flip character $0$ to $1$ or vice versa) so that the resulting string can be split into no more than $k$ substrings, where each substring contains only characters $0$ or only characters $1$.
Requirement: Determine the minimum number of characters in the string $S$ that need to be flipped.
### Input
- Line 1 contains two positive integers $n, k \le 2 \cdot 10^5$ separated by a space.
- Line 2 contains the string $S$ (consisting of $n$ characters $\in$ $\\{0,1\\}$ written consecutively).
### Output
- Print a single integer which is the minimum number of characters in the string $S$ that need to be modified.
### Constraints
- Subtask 1 ($20$% of the points): $n \le 20$
- Subtask 2 ($20$% of the points): $n,k \le 400$
- Subtask 3 ($20$% of the points): $n \le 2\cdot10^5,k \le 400$
- Subtask 4 ($20$% of the points): $n \le 2\cdot10^5,k \le 5000$
- Subtask 5 ($20$% of the points): No additional constraints beyond those stated in the problem.
### Example
Input:
```
10 1
1000100011
```
Output:
```
4
```
Input:
```
6 2
010110
```
Output:
```
2
```
