AT_nomura2020_e Binary Programming

[problemUrl]: https://atcoder.jp/contests/nomura2020/tasks/nomura2020_e 高橋くんは、空文字列 $ S $ と、$ 0 $ で初期化された変数 $ x $ を持っています。 また `0` および `1` のみからなる文字列 $ T $ があります。 高橋くんはこれから、以下の $ 2 $ ステップからなる操作を $ |T| $ 回繰り返します。 - $ S $ の好きな位置に `0` または `1` を挿入する。 - 次に、$ S $ の左から奇数番目に書かれた数字の総和を $ x $ に加算する。例えば現在 $ S $ が `01101` であるなら、$ S $ の左から奇数番目に書かれた数字は左から `0`, `1`, `1` なので、$ 2 $ を $ x $ に加算する。 最終的に $ S $ が $ T $ に一致するような操作列における、最終的な $ x $ の値の最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ T $

最終的に $ S $ が $ T $ に一致するような操作列における、最終的な $ x $ の値の最大値を出力せよ。

### 制約 - $ 1\ \leq\ |T|\ \leq\ 2\ \times\ 10^5 $ - $ T $ は `0` および `1` のみからなる。 ### Sample Explanation 1 例えば以下のような操作列が、最終的な $ x $ の値を $ 5 $ に最大化します。 - $ S $ の先頭に `1` を挿入する。$ S $ は `1` になり、$ x $ に $ 1 $ を加算する。 - $ S $ の $ 1 $ 文字目の直後に `0` を挿入する。$ S $ は `10` になり、$ x $ に $ 1 $ を加算する。 - $ S $ の $ 2 $ 文字目の直後に `1` を挿入する。$ S $ は `101` になり、$ x $ に $ 2 $ を加算する。 - $ S $ の先頭に `1` を挿入する。$ S $ は `1101` になり、$ x $ に $ 1 $ を加算する。