Longest Beautiful Subsequence

Given a binary sequence consisting solely of characters '0' and '1' (with at least one '1' present), remove some elements (possibly none) such that the remaining subsequence forms the longest beautiful sequence.

A sequence is considered beautiful if it has the form \(0^m1^n\) with \(m \ge 0\) and \(n > 0\); that is, all the 0's (if any) appear before any 1's. The order of elements in the subsequence must remain the same as in the original sequence.

For example, given the sequence 01011, one optimal beautiful subsequence is 0011 of length 4.

inputFormat

The input consists of a single line containing a non-empty string of characters '0' and '1'. It is guaranteed that the string contains at least one '1'.

outputFormat

Output a single integer: the length of the longest beautiful subsequence obtainable from the input string.

sample

1010

2