Saat mexanizminin zəngi

Dovşanlar — Vikipediyaya görə, dovşankimilər dəstəsinə aid olan dovşanlar ailəsindən kiçik məməlilərdir. Bu doğrudur. Buna görə də, onlar darıxdırıcı deyillər, çünki hamısı orijinal və yaxşı təşkil olunmuşdur. Fermamızdakı dovşanlar, sərhədləri mürəkkəb çiçək naxışları ilə bəzədilmiş qorunan qəfəslərdə yaşayırlar. Qəfəslərdə çoxlu cazibədar narıncı yerkökü kolları yetişir. Dovşanlar sürətlə çoxalır (bu normaldır, hər il dovşan orduları doğulur) və müəllimlərimiz onları qəfəslərdə asanlıqla izləməyə çalışırlar.

Qəfəslər nizamlı şəkildə təşkil olunub — onlar bir düz sıranı təşkil edir. İlk çoxalma mövsümünün əvvəlində bəzi qəfəslər boş ola bilər. Hər çoxalma mövsümünün sonunda yaxşı koordinasiya olunmuş dovşan köçürülməsi həyata keçirilir. Köçürülmə, hər mövsüm üçün istənilən şəkildə seçilə bilən müsbət tam parametr $k$-dən asılı olan sadə bir düsturla tənzimlənir. Köçürülmə bütün qəfəslər üçün paralel şəkildə həyata keçirilir. Hər bir qəfəsdə təxminən yarısı dovşanlar çıxarılır və sıranın $k$ qəfəs aşağısına köçürülür. Hədəf qəfəsin dolu olub-olmaması əhəmiyyətli deyil.

Əgər qəfəs sıranın sonunda çox yaxın yerləşirsə (sıranın $k$ qəfəsindən az aşağı), bütün dovşanlar qəfəsdə qalır və heç yerə köçürülmür. Hər hansı bir qəfəs sonsuz sayda dovşan saxlaya bilər və hər hansı dolu qəfəsdə uğurlu çoxalma üçün həmişə kifayət qədər dovşan var.

İlk çoxalma mövsümünün əvvəlində dovşanların yerləşdiyi və boş olan qəfəsləri göstərən başlanğıc yerləşmə verilir. Bütün qəfəslərin dovşanlarla dolu olması üçün lazım olan minimum köçürmə sayını müəyyən edin.

Giriş verilənləri

Uzunluğu $b(1\le b\le 40)$ olan bir sıra verilir, burada hər bir simvol bir qəfəsi təmsil edir və ya $0$ (boş qəfəs) və ya $1$ (dolu qəfəs) olur. İlk simvol sıradakı ilk qəfəsə uyğundur.

Çıxış verilənləri

Bütün qəfəslərin dovşanlarla dolu olması üçün lazım olan minimum köçürmə sayını çıxarın. Əgər hər hansı köçürmə sayında bütün qəfəsləri doldurmaq mümkün deyilsə, $-1$ çıxarın.

Nümunələr