题目描述

译自 [CERC2018] Clockwork ||ange

据百度百科，兔是哺乳类兔形目兔科下属所有的属的总称。毋庸置疑的是，这段文字不是无聊的，因为它们是原始的，并且组织良好。我们农场的兔子生活在有保护的畜栏里，畜栏的边界装饰有精美的花卉装饰品。畜栏里生长着数十个可爱的橙色胡萝卜。兔子繁殖很快（这很正常，每年都有成千上万的兔子出生），我们的导师希望不费力地把它们安置在畜栏里。

畜栏规则地形成一排。在第一个繁殖季开始时，一些畜栏里可能没有兔子。每个繁殖季结束时，都会进行一次精心策划过的兔子搬迁。搬迁遵循一条简单的公式，这个公式取决于一个正整数 $K$，不同的繁殖季 $K$ 值不一定相同。对于所有畜栏，搬迁工作同时进行。在每个畜栏中，大约有一半的兔子被移到这个畜栏右边第 $K$ 个畜栏里。目标畜栏里原来有没有兔子都没有关系。

如果畜栏离这一排最后一个畜栏太近（即离最后一个畜栏的距离小于 $K$ ），那么这个畜栏中的所有兔子都留在原畜栏，不会进行搬迁。

每个畜栏都可以容纳无限只兔子，并且非空的畜栏中总有足够多能够成功繁殖的兔子。

给定第一个繁殖季开始时畜栏被占用的情况。请求出使得所有畜栏中都有兔子的最少搬迁次数。

输入格式

输入仅有一行，包含一个长度为 $b$ 的字符串，每个字符表示一个畜栏。字符只有 $0$（空畜栏）和 $1$（有兔子的畜栏）两种。第一个字符表示这一排的第一个畜栏。

输出格式

输出使得所有畜栏中都有兔子的最少搬迁次数。如果没有任何一种搬迁方案使得每个畜栏中都有兔子，输出 $-1$。

1010

1

100110000

3

提示

$1≤b≤40$