Вам дана бинарная строка $$$s_1s_2 \ldots s_n$$$, содержащая хотя бы одну 1. Вы хотите получить бинарную строку такой же длины, состоящую только из 1. Для этого вы можете применять следующую операцию любое количество раз:

Выберем число $$$d$$$ ($$$1 \le d \le n$$$) и рассмотрим в качестве строки $$$t$$$ циклический сдвиг строки $$$s$$$ вправо на $$$d$$$, или, более формально, $$$t = s_{n - d + 1} \ldots s_{n}s_{1} \ldots s_{n - d}$$$. После этого для всех $$$j$$$, для которых выполняется $$$t_j = 1$$$, выполним $$$s_j := 1$$$. Описанная операция стоит $$$d$$$ монет, где $$$d$$$ — величина выбранного сдвига.

Обратите внимание, что те позиции $$$j$$$ строки $$$s$$$, для которых изначально выполнялось $$$s_j=1$$$, остаются равными $$$1$$$ даже при $$$t_j=0$$$.

Требуется определить, какое минимальное количество монет можно потратить, чтобы строка $$$s$$$ после всех операций состояла только из 1.