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.


Submitting to 'K-tuple Flip'


You're not logged in! Click here to login


Submitting to 'K-tuple Flip'


You're not logged in! Click here to login


Submitting .cpp to 'K-tuple Flip'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 4
Your best score: 0
Source: TROC 24 (errorgorn)

Subtask Score
1 100