output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: input = input()
  min = 10000000000000000
  nums = [""]
  for c in input:
      newnums = []
      if c == "0" or c == "1":
          for i in range(len(nums)):
              newnums.append(nums[i] + c)
      else:
          for i in range(len(nums)):
              newnums.append(nums[i] + "0")
              newnums.append(nums[i] + "1")
      nums = newnums
  for num in nums:
      gap = 0
      max = 0
      min = 0
      for c in num:
          if c == "0":
              gap += 1
              max = gap if gap > max else max
          elif c == "1":
              gap -= 1
              min = gap if gap < min else min
      x = max - min
      min = x if x < min else min
  min = 0 - min if min < 0 else min
  print(min)
  
problem_description: Statement
  
  Given is a string S, where each character is `0`, `1`, or `?`.
  
  Consider making a string S' by replacing each occurrence of `?` with `0` or
  `1` (we can choose the character for each `?` independently). Let us define
  the unbalancedness of S' as follows:
  
    * (The unbalancedness of S') = \max \\{ The absolute difference between the number of occurrences of `0` and `1` between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\\}
  
  Find the minimum possible unbalancedness of S'.
samples: [{"input": "0??", "output": "1\n    \n\nWe can make S'= `010` and achieve the minimum possible unbalancedness of 1.\n\n* * *"}, {"input": "0??0", "output": "2\n    \n\n* * *"}, {"input": "??00????0??0????0?0??00??1???11?1?1???1?11?111???1", "output": "4"}]