Description

Translated from [CERC2018] Clockwork ||ange.

According to Baidu Baike, rabbits are a general name for all genera under the family Leporidae in the order Lagomorpha of mammals. Needless to say, this text is not boring, because they are primitive and well organized. The rabbits on our farm live in protected pens, and the borders of the pens are decorated with beautiful floral ornaments. Dozens of lovely orange carrots grow in the pens. Rabbits reproduce quickly (which is normal: thousands of rabbits are born every year), and our supervisor wants to place them into the pens effortlessly.

The pens form a row regularly. At the beginning of the first breeding season, some pens may have no rabbits. At the end of each breeding season, there is a carefully planned rabbit relocation. The relocation follows a simple rule that depends on a positive integer $K$, and the value of $K$ does not have to be the same in different breeding seasons. For all pens, the relocation happens simultaneously. In each pen, about half of the rabbits are moved to the pen that is the $K$-th pen to the right of this pen. It does not matter whether the target pen originally has rabbits or not.

If a pen is too close to the last pen in the row (that is, its distance to the last pen is less than $K$), then all rabbits in this pen stay in the original pen, and no relocation is performed.

Each pen can hold infinitely many rabbits, and every non-empty pen always has enough rabbits that can reproduce successfully.

Given the occupancy of the pens at the beginning of the first breeding season, find the minimum number of relocations needed so that every pen has rabbits.

Input Format

The input contains only one line: a string of length $b$, where each character represents a pen. The characters are only $0$ (empty pen) and $1$ (pen with rabbits). The first character represents the first pen in the row.

Output Format

Output the minimum number of relocations needed so that every pen has rabbits. If there is no relocation plan that can make every pen have rabbits, output $-1$.

1010

1

100110000

3

Hint

Constraints: $1 \le b \le 40$.

Translated by ChatGPT 5