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.