配点 : $900$ 点

問題文

高橋くんは、空文字列 $S$ と、$0$ で初期化された変数 $x$ を持っています。

また 0 および 1 のみからなる文字列 $T$ があります。

高橋くんはこれから、以下の $2$ ステップからなる操作を $|T|$ 回繰り返します。

• $S$ の好きな位置に 0 または 1 を挿入する。
• 次に、$S$ の左から奇数番目に書かれた数字の総和を $x$ に加算する。例えば現在 $S$ が 01101 であるなら、$S$ の左から奇数番目に書かれた数字は左から 0, 1, 1 なので、$2$ を $x$ に加算する。

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

制約

• $1 \leq |T| \leq 2 \times 10^5$
• $T$ は 0 および 1 のみからなる。

入力

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

$T$

出力

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

1101

5

例えば以下のような操作列が、最終的な $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$ を加算する。

0111101101

26