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 <bits/stdc++.h>
using namespace std;
#define int long long
inline void read (int &x) {
	char ch = getchar(); x = 0;
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 2e5 + 10; 
int n, a[N], b[N], s, ca[N], cb[N], res; char ch[N]; vector<int> v;
signed main() {
	scanf ("%s", ch + 1); n = strlen (ch + 1); int t = 1;
	for (int i = 1; i <= n; ++i) s += ch[i] - 48;
	for (int i = n; i >= 1; --i) ca[i] = ca[i + 1] + (ch[i] == '0');
	for (int i = 1; i <= n; ++i) cb[i] = cb[i - 1] + (ch[i] == '0');
	for (int i = 1; i <= n; ++i) {
		if (ch[i] == '1') res += (cb[i] + (i % 2 == 0)) / 2 + ca[i] * (t & 1) + (i & 1);
		else t = 0; ++t;
	//	if (ch[i] == '1') printf ("%lld\n", (cb[i] + (i % 2 == 0)) / 2 + ca[i] + (i & 1));
	} res += ((s - 1) / 2 + 1) * ((s - 1) / 2) + (s % 2 == 0) * (s / 2);
//	printf ("%lld %lld\n", s, ((s - 1) / 2 + 1) * ((s - 1) / 2) + (s % 2 == 0) * (s / 2));
	return printf ("%lld\n", res), 0;
}