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 <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=2e5+10;
char S[N];
int n;
int main() {
	scanf("%s",S+1); n=strlen(S+1);
	int tot=0;
	for(int i=1;i<=n;++i)
		tot+=S[i]=='1';
	int x=0,y=0;
	ll res=0;
	for(int i=1;i<=n;++i) {
		if(S[i]=='0') ++x;
		else {
			int j=i; while(j+1<=n&&S[j+1]=='1') ++j;
			if(j-i+1&1) {
				if(!(x+y&1)) res+=(x+1>>1);
				else res+=(x>>1);
				res+=(n-tot)-x;
				y^=1;
			}
			res+=1ll*(j-i+1>>1)*(n-tot);
			i=j;
		}
	}
	if(tot&1) res+=(tot+1>>1),tot--;
	for(int i=tot;i;i-=2) res+=i;
	printf("%lld",res);
	return 0;
}