题目描述

高橋くんは、空文字列 $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$ の値の最大値を出力せよ。

题目大意

给定目标串 $S$，初始有一个空串 $T$，每次可以往 $T$ 中的任意位置插入一个字符（0 或 1），并且会增加 $T$ 的所有奇数位的字符和，对应的贡献。

要求最后 $T=S$。求出最大贡献和。

translated by Rick Astley。

1101

5

0111101101

26

提示

制約

• $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$ を加算する。