题目描述

高桥君有一个空字符串 $S$，以及一个初始值为 $0$ 的变量 $x$。

此外，他还有一个只由 0 和 1 组成的字符串 $T$。

高桥君将进行 $|T|$ 次如下的两步操作：

• 在 $S$ 的任意位置插入一个 0 或 1。
• 然后，将 $S$ 中从左起奇数位置上的数字之和加到 $x$ 上。例如，如果当前 $S$ 为 01101，那么从左起奇数位置上的数字依次为 0、1、1，因此将 $2$ 加到 $x$ 上。

请输出最终 $S$ 与 $T$ 相同的所有操作序列中，最终 $x$ 的最大可能值。

输入格式

输入为以下格式，从标准输入读取：

$T$

输出格式

请输出最终 $S$ 与 $T$ 相同的所有操作序列中，最终 $x$ 的最大可能值。

输入输出样例 #1

输入 #1

1101

输出 #1

5

输入输出样例 #2

输入 #2

0111101101

输出 #2

26

说明/提示

限制条件

• $1 \leq |T| \leq 2 \times 10^5$
• $T$ 只包含字符 0 和 1。

样例解释 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$。