Programming contests

DEIK Regionális Programozó Csapatverseny, nyílt kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

Bitstring

You are given a b bitstring (so a number sequence containing only 0s and 1s). You may change one of the 0s to a 1. This operation is called bit-flipping.
Your task is to find the longest consecutive sequence of 1s in a given bitstring after potentionally performing exactly one bit-flip.

Input

The input is exactly one line which contains a b bitstring (containing only 0s and 1s).

Output

The output is a single integer which is the length of the longest subsequence containing only 1s after performing at most 1 bit-flipping.

Restrictions

  • The number of characters (bits) in b is at most 1000;
  • b contains at most one 0.

Example

Input:
  1. 11011101111
download as text file Output:
  1. 8
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019