from sortedcontainers import SortedList

class Solution:
    def minimumWhiteTiles(self, listC: str, nC: int, lC: int) -> int:
        nD = len(listC)
        if nC*lC>=nD:       return 0
        listI = SortedList(i for i,c in enumerate(listC) if c=='1')
        nW = len(listI)
        if nW==nD:          return nD-nC*lC
        l,r = 0,nW
        listK = [0]*nW
        listC = [0]*nW
        for i,I in enumerate(listI):
            j = listI.bisect_right(I+lC-1)
            listK[i] = j
            listC[i] = j-i
        
        dp = [0]*(nW+1)
        for c in range(nC):
            dpN = deepcopy(dp)
            for i in range(nW):
                dpN[listK[i]] = max(dpN[listK[i]],dp[i]+listC[i])
            dp = list(accumulate(dpN,max))
        return nW-dp[-1]