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>
#define maxn 1000000000000000LL
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,i,sum,top,a[200005],b[200005],c[200005],ans,sum0,sum1,ture1;
long long top2,now,d[200005],e[200005],sum2[200005];
char s[200005];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	s[0]='0';
	for(i=1;i<=n;i++)
		if(s[i]=='0')
			sum++;
		else{
			if(s[i-1]=='0'){
				top++;
				c[top]=(i&1);
				b[top]=1;
				a[top]=sum;
				sum=0;
			}
			else
				b[top]++;
		}
	if(top==0){
		pus(0,2);
		return 0;
	}
	sum0=sum;
	for(i=1;i<=top;i++){
		sum0+=a[i];
		sum1+=b[i]/2;
		ture1+=b[i];
	}
	ans=(sum0+1)*sum1;
	ture1--;
	if(ture1&1)
		ans+=ture1/2+1;
	ture1/=2;
	ans+=ture1*(ture1+1);
	//pus(ans,2);
	for(i=1;i<=top;i++)
		if(b[i]&1){
			top2++;
			d[top2]+=a[i];
			e[top2]=c[i];
		}
		else
			d[top2+1]+=a[i];
	for(i=top2;i>=1;i--){
		sum2[i]=sum2[i+1]+e[i];
		ans+=e[i];
	}
	//pus(ans,2);
	for(i=1;i<=top2;i++)
		if((e[i]^now)==0){
			d[i]--;
			now^=1;
			if(now==0)
				ans+=sum2[i]+i-1;
			else
				ans+=top2-sum2[i];
		}
	//pus(ans,2);
	sum2[top2+1]=sum+d[top2+1];
	for(i=top2;i>=1;i--)
		sum2[i]=sum2[i+1]+d[i];
	sum=0;
	for(i=1;i<=top2;i++){
		sum+=d[i];
		ans+=sum2[i+1]+sum/2;
	}
	pus(ans,2);
	//for(i=1;i<=top;i++)
	//	cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
    return 0;
}