비트 문자열 뒤집기

길이가 $N$이고 0과 1로만 이루어진 문자열 $S$와 정수 $M$이 주어진다. $M$은 $N$의 약수이다.

$S$에 적용할 수 있는 연산은 다음 세 가지이다.

• 문자 하나를 뒤집는다. 0은 1이 되고, 1은 0이 된다.
• 양의 정수 $k$를 골라 처음 $k \times M$개의 문자를 뒤집는다. 이때 $k \times M \le N$이어야 한다.
• 양의 정수 $k$를 골라 마지막 $k \times M$개의 문자를 뒤집는다. 이때 $k \times M \le N$이어야 한다.

처음 $N$개를 뒤집는 연산과 마지막 $N$개를 뒤집는 연산은 결과가 같으므로 한 가지로 센다.

예를 들어 $S$가 "110100001001"이고 $M = 4$이면 $S$에 적용할 수 있는 연산은 모두 17가지이다. 두 번째 문자를 뒤집으면 "100100001001"이 되고, 처음 $2 \times M$개를 뒤집으면 "001011111001"이 되며, 마지막 $M$개를 뒤집으면 "110100000110"이 된다.

$S$의 모든 문자를 1로 만들기 위해 적용해야 하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 $S$가 주어진다. $S$는 0과 1로만 이루어져 있고, 길이 $N$은 1 이상 2500 이하이다.

둘째 줄에 정수 $M$이 주어진다. $M$은 $N$의 약수이다.

첫째 줄에 $S$의 모든 문자를 1로 만들기 위해 적용해야 하는 연산의 최소 횟수를 출력한다.