E - Self-contained Editorial /

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.