cho.sh

Flipping a Bit String

Given a binary string and a divisor M of its length, find the minimum number of operations (single flip, prefix flip of a multiple of M, or suffix flip of a multiple of M) to make all characters 1.

Hard8Dynamic programmingGreedyStringNo attempts yetTime limit2sMemory limit512 MB

Problem

You are given a string SS of length NN made up of 0 and 1 only, together with an integer MM. MM divides NN.

Three operations can be applied to SS.

  • Flip one character. A 0 becomes a 1, and a 1 becomes a 0.
  • Choose a positive integer kk and flip the first k×Mk \times M characters. Here k×M≤Nk \times M \le N must hold.
  • Choose a positive integer kk and flip the last k×Mk \times M characters. Here k×M≤Nk \times M \le N must hold.

Flipping the first NN characters and flipping the last NN characters give the same result, so they count as one operation.

For example, if SS is "110100001001" and M=4M = 4, there are 17 operations that can be applied to SS. Flipping the second character gives "100100001001", flipping the first 2×M2 \times M characters gives "001011111001", and flipping the last MM characters gives "110100000110".

Write a program that finds the minimum number of operations needed to turn every character of SS into 1.

Input

The first line contains the string SS. It consists of 0 and 1 only, and its length NN satisfies 1≤N≤25001 \le N \le 2500.

The second line contains the integer MM, a divisor of NN.

Output

Print the minimum number of operations needed to turn every character of SS into 1.