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 cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
char str[200005];
int main() {
	scanf("%s", str);
	int n = strlen(str);
	int las = 0;
	int ones = 0, blocks = 0;
	string s;
	for (int i = 0; i < n; ++i) {
		if (str[i] == '1') ++ones;
		else s += '0';
		if (str[i] != str[i + 1]) {
			if (str[i] == '1') {
				int len = i - las + 1;
				if (len & 1) s += '1';
				blocks += len / 2;
			}
			las = i + 1;
		}
	}
	int zeros = n - ones;
	ll ans = 0;
	for (int i = 1; i <= ones; ++i) ans += (i + 1) / 2;
	ans += (ll)zeros * blocks;
	int cur = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '1') {
			if ((i + 1) & 1) ans += (cur + 1) / 2;
			else ans += cur / 2;
			ans += zeros - cur;
		} else ++cur;
	}
	printf("%lld\n", ans);
}