Pattern: 3dsa + 12 MCQS 90 min

You are given a binary string S and an integer K. You are allowed to perform at most K flip operations (changing a 0 to a 1 or a 1 to a 0). Find the minimum number of inversions the string can have after performing at most K flips.

(Note: An inversion in a binary string is a pair of indices (i,j) such that i < j and S[i] > S[j], i.e., a 1 appears before a 0.)

Input Format

The first line contains the binary string S. The second line contains the integer K.

Output Format

Print a single integer representing the final number of inversions.

Examples

Example 1:

Input:

• S: 0110
• K: 1 Output:
• 2

Example 2:

Input:

• S: 0110
• K: 3 Output:
• 0