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
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	string S;
	cin >> S;
	N = S.size();
	vector<int> A(N, 0);
	int res = 0;
	int t = 0;
	int cur = 0;
	int tot = 0;
	for (int i = 0; i < N; i++) {
		if (t == 0 && S[i] == '1') {
			A[i] = 1;
			cur++;
			tot++;
			res += cur;
			t = 1;
		} else if (t == 1) {
			A[i] = 1;
			tot++;
			res += cur;
			t = 0;
		}
	}
	int X[2];
	X[0] = 0;
	X[1] = 0;
	//cerr << res << endl;
	for (int i = N - 1; i >= 0; i--) {
		swap(X[0], X[1]);
		if (S[i] == '1') {
			X[0]++;
		}
		if (A[i] == 1) {
			tot--;
		} else {
			cur += X[tot % 2];
			cur -= X[(tot + 1) % 2];
			res += cur;
		}
		
		//cerr << res << endl;
	}

	cout << res << endl;
}