Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of `0` and `1`.

Now, Takahashi will do the operation with the following two steps |T| times.

* Insert a `0` or a `1` at any position of S of his choice.
* Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is `01101`, the digits in the odd positions are `0`, `1`, `1` from left to right, so x is incremented by 2.



Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

* 1 \leq |T| \leq 2 \times 10^5
* T consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


T


Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Examples

Input

1101


Output

5


Input

0111101101


Output

26
#include <cstdio>
#include <cstring>

typedef long long LL;
const int MN = 200005;

int N, C0, C1, K;
char T[MN];
int stk[MN], cnt[MN], tp;
LL Ans;

int main() {
	scanf("%s", T + 1), N = strlen(T + 1);
	for (int i = 1; i <= N; ++i) ++(T[i] & 1 ? C1 : C0);
	Ans = (LL)(C1 + 1) * (C1 + 1) / 4;
	T[0] = T[N + 1] = '0';
	for (int i = 0; i <= N + 1; ++i) {
		int x = T[i] - '0';
		if (!x) {
			if (tp && !stk[tp]) ++cnt[tp];
			else stk[++tp] = 0, cnt[tp] = 1;
		} else {
			if (tp && stk[tp]) --tp, Ans += C0;
			else stk[++tp] = 1, cnt[tp] = 1;
		}
	} --cnt[1], --cnt[tp];
	for (int i = 1, s = 0; 2 * i <= tp; ++i)
		s += cnt[2 * i - 1],
		Ans += (s + i + 1) / 2 - (i + 1) / 2 + (C0 - s);
	printf("%lld\n", Ans);
	return 0;
}