Биты опасны

Вы думаете, что убежать из сна легко? Это не тот случай, когда сон о битах. Вы наверняка вчера читали слишком много теории, но это уже не имеет значения. Единственное, что Вам хочется, так это проснуться. Вы, наверное, неправильно вычислили наилучшую специальную строку... или они только что обманули Вас. Длинная строка битов все еще находится перед Вашими закрытыми глазами.

Потом Вы поняли, что у Вас имеется возможность изменить самый левый бит этой строки с 0 на 1, или с 1 на 0. Это стоит в точности четыре секунды, но Вы это можете сделать!

Потом Вы обнаружили, что можете также сдвинуть циклически строку на одну позицию влево или на одну позицию вправо. Любое из этих действий занимает семь секунд в Вашем странном сне.

Что-то подсказывает Вам, что именно 1-биты держат Вас во сне. Если вдруг это правда, то Вы решили превратить всю строку в нули. У Вас имеется все для этого необходимое.

Но сколько времени потребуется на это, если действовать оптимально?

Входные данные

Единственная строка S (2 ≤ |S| ≤ 2∙10^5), состоящая из нулей и единиц.

Выходные данные

Вывести наименьшее время, за которое можно преобразовать S в строку из одних нулей, в секундах.

Примеры

Примечание

В первом тесте оптимальной будет следующая стратегия: изменим левый бит: 01001, сдвинем строку циклически влево: 10010, изменим левый бит: 00010, сдвинем строку циклически вправо: 00001, сдвинем строку циклически вправо (снова): 10000, изменим левый бит: 00000. Три изменения и три циклических сдвига займут в точности 33 секунды.