Time Limit: 3 sec / Memory Limit: 1024 MB
Score : 100 points
Problem Statement
Ao loves certain sets of non-negative integers.
Let X be a set of non-negative integers. Whether she loves X or not is determined as follows:
- If X is the empty set, she loves X.
- If, for any (possibly the same) two elements u and v in X, at least one of u+v and {\rm abs}(u-v) is contained in X, she loves X.
- If none of the above conditions is satisfied, she does not love X.
You are a big fan of Ao, and going to present her a set of non-negative integers. Currently you have a set A of non-negative integers. You want to erase (possibly zero) elements from A so that she loves the set of remaining integers. You also want to maximize the number of remaining integers. What is the largest number of remaining integers?
Constraints
- A is not empty.
- The largest element in A is not larger than 500,000
Input
Input is given from Standard Input in the following format:
S
Here, S=S_0S_1...S_{|S|-1} is the string which indicates A.
For each i ( 0 \leq i \leq |S|-1 ), S_i = 1
if A contains i and S_i = 0
if not.
It is guaranteed that S_{|S|-1} is 1
.
Output
Print the largest number of remaining integers.
Sample Input 1
1000001001011
Sample Output 1
3
The set A = \{0,6,9,11,12\}. If you erase 9 and 11, Ao loves the set of remaining integers: \{0,6,12\}.
Sample Input 2
10110110101
Sample Output 2
4
Sample Input 3
0111
Sample Output 3
0
The set of remaining integers must be empty.