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
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
const int maxn = 1<<19, mod = 1e9 + 7;
string t;
int n, cnt[maxn], val[maxn], sz = 0;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> t;
	for(auto &i : t) {
		if(i == '1') ++sz, val[sz] = sz&1;
		else cnt[sz]++;
	}
	ll ans = 0;
	for(int i = 1; i <= sz; i++) ans += (i+1)/2;
	{
		int c[2], p = 0, rev = 0;
		c[0] = count(val+1, val+sz+1, 0);
		c[1] = count(val+1, val+sz+1, 1);
		for(int i = 0; i < sz; i++) {
			//cout << i << " " << c[0] << " " << c[1] << " " << p << '\n';
			if(cnt[i] && (val[i+1] ^ rev ^ 1)) {
				cnt[i]--;
				rev ^= 1;
				swap(c[0], c[1]);
				ans += p + c[1];
				//cout << c[0] << " " << c[1] << " " << p << '\n';
			}
			val[i+1] ^= rev;
			p += val[i+1];
			c[val[i+1]]--;
			//cout << i << " " << ans << '\n';
		}
	}
	{
		int c[2] = {0, 0}, x = count(val, val+sz+1, 1);
		for(int i = sz; i >= 0; i--) {
			if(cnt[i]&1) {
				swap(c[0], c[1]);
				ans += c[1] + x;
				cnt[i]--;
			}
			//cout << i << " " << ans << '\n';
			ans += (c[0] + c[1]) * 1ll * (cnt[i] / 2) + cnt[i] * 1ll * x;
			c[val[i]]++;
			x -= val[i];
			//cout << i << " " << ans << '\n';
		}
	}
	cout << ans;
}
