K-tuple Flip

Description

There is a binary string $S$ of length $N$. In one operation, you choose an index $i$ ($1 \le i \le N$) and flip $S_i$. More formally:

• If $S_i$ was initially $\texttt{0}$, then set $S_i$ to $\texttt{1}$.
• If $S_i$ was initially $\texttt{1}$, then set $S_i$ to $\texttt{0}$.

Define the inversion count of a binary string as the number of pairs $(i,j)$ such that $1 \le i < j \le N$, $S_i=\texttt{1}$ and $S_j=\texttt{0}$.

Find the minimum inversion count of $S$ after performing at most $K$ operations.

Constraints

• $1 \leq K \leq N \leq 2000$

Input

N K
S1S2…SN

Output

An integer representing the minimum inversion count of $S$after performing at most $K$operations.

Sample Input 1

10 2
1111010001

Sample Output 1

9

Sample Input 2

3 3
011

Sample Output 2

0

Sample Input 3

3 1
100

Sample Output 3

0

Explanation

In the first sample, we use $2$ operations with $i=8$ then $i=9$ so that $S$ becomes $\texttt{1111010111}$. The inversion count here is $9$ and we can show that it is the minimum inversion count.

In the second sample, we use $2$ operations with $i=3$ then $i=3$ so that $S$ becomes $\texttt{011}$. The inversion count here is $0$ and it is clearly the minimum inversion count.