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?


  • A is not empty.
  • The largest element in A is not larger than 500,000


Input is given from Standard Input in the following format:


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.


Print the largest number of remaining integers.

Sample Input 1


Sample Output 1


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


Sample Output 2


Sample Input 3


Sample Output 3


The set of remaining integers must be empty.