Minimizing Ones

You are given a binary string consisting of characters '0' and '1'. You are allowed to perform the following operation any number of times (possibly zero):

Find a substring that matches the pattern \( 1(01)^k,\quad k \ge 1 \) —that is, a substring of odd length which starts with a 1, then alternates between 0 and 1 and finally ends with a 1—and replace it with the substring \( 0(10)^k \) (which is of the same length). Note that this operation decreases the number of ones by exactly 1.

Your task is to apply the operations in an optimal way so that the final number of ones is minimized, and output that minimum number.

Observation (informal): In any optimal sequence of operations, one may eventually merge separate groups of ones (originally separated by a single zero) into one single one. More precisely, if two contiguous segments of ones (maximal blocks in the original string) are separated by exactly one zero, then operations can merge them into a single one. However, if a block of ones stands alone (or is separated by at least two zeros from its neighbors) then no operation is possible within that block. Thus the answer is the sum of contributions from each part: for every two or more blocks that are joinable (i.e. separated by exactly one zero), they can be merged and contribute 1 to the answer, and an isolated block contributes the number of ones it originally contained.

inputFormat

The input consists of a single line containing a non‐empty binary string.

Format: A string S of characters '0' and '1'.

outputFormat

Output a single integer, the minimum number of ones that can remain after performing the operations optimally.

Format: An integer.

sample

0

0