시계태엽 오렌지

토끼는 토끼목 토끼과에 속하는 작은 포유류다. 위키백과에 그렇게 적혀 있다. 틀린 말이 아니다. 따라서 토끼가 지루할 리도 없다. 모두 독창적이고 잘 정돈되어 있기 때문이다. 우리 농장의 토끼들은 울타리 테두리에 정교한 꽃 장식이 달린 우리에서 산다. 우리 안에는 사랑스러운 주황색 당근 다발이 잔뜩 자란다. 토끼는 번식이 빠르고(매년 무리가 태어나는 것이 당연하다), 우리의 스승은 토끼를 우리에 수월하게 배치하기를 바란다.

우리들은 잘 정돈되어 한 줄로 나란히 놓여 있다. 첫 번째 번식기가 시작될 때 일부 우리는 비어 있을 수 있다. 각 번식기가 끝나면 잘 짜인 토끼 재배치가 이루어진다. 재배치는 시즌마다 임의로 고를 수 있는 양의 정수 매개변수 K 하나에 따라 결정되는 단순한 공식을 따른다. 재배치는 모든 우리에 동시에 적용된다. 각 우리에서 토끼의 약 절반이 우리에서 빠져나와 우리 줄에서 K칸 아래로 이동한다. 이동한 우리에 이미 토끼가 있든 없든 상관없다.

어떤 우리가 줄의 끝에 너무 가까워서(줄에서 아래로 K칸이 안 되는 경우) 그 아래에 우리가 K개 미만이면, 모든 토끼는 그 우리에 그대로 남고 아무 데도 이동하지 않는다. 어떤 우리든 토끼를 무한히 수용할 수 있고, 비어 있지 않은 우리에는 언제나 번식에 충분한 토끼가 있다.

첫 번째 번식기가 시작될 때 어떤 우리가 점유되어 있고 어떤 우리가 비어 있는지 주어진다. 모든 우리를 토끼로 채우는 데 필요한 최소 재배치 횟수를 구하라.

입력은 한 줄로 주어지며, 길이 b인 문자열(1 ≤ b ≤ 40)로 이루어진다. 각 문자는 우리 하나를 나타내고 0(빈 우리) 또는 1(토끼가 사는 우리)이다. 첫 번째 문자는 줄의 첫 번째 우리에 대응한다.

모든 우리를 토끼로 채우는 데 필요한 최소 재배치 횟수를 출력한다. 어떤 횟수의 재배치로도 모든 우리를 채울 수 없다면 −1을 출력한다.