Telecommunication Network

0

0 votes
Problem

You are the chief incharge of Telecommunication India.
Your company has decided to expand its reach to n villages. 

So you have to connect all the villages to the Telecommunication network. However it is not always possible to build a tower at some villages due to the sandy land.

You have two options : 
You can either connect a village with a large landline cable or you build a tower here for connection. Both costs i amount for the i-th village.

The range of each tower is m. That means, if you build a tower at j-th village, then you can connect all the villages with index number (j-m) to (j+m) villages both inclusive provided they are a valid village from 1 to n.

Calculate the minimum total cost of connecting all the villages to the Telecommunication network.


INPUT
The first line of integer contains two integers n and m.
The second line contains a binary string of length n. if the i-th character is 1 then you can build a tower here otherwise you cannot build any tower.


OUTPUT
Print the minimum total amount of connecting all the villages to the Tele-network.

 

Constraints :

1 <= N,K <= 2 • 10^5

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?