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
//https://atcoder.jp/contests/nomura2020/tasks/nomura2020_e
#include<bits/stdc++.h>
using namespace std;
#define nn 65536*4
#define int long long

int fullcombo(int x){
	int ans=0;for(int i=1;i<=x;i++) ans+=(i+1)/2;
	return ans; 
}
char str[nn];int n;vector<int> all;

int len[nn],m;
namespace trcyx{
	int len[nn*2],tag[nn*2],sum[nn*2];
	#define lc id<<1
	#define rc id<<1|1
	#define mid (l+r)/2
	void build(int l,int r,int id){
		len[id]=r-l+1;tag[id]=0;sum[id]=0;
		if(l<r) build(l,mid,lc),build(mid+1,r,rc);
	}
	void up(int id){
		sum[id]=sum[lc]+sum[rc];
	}
	void flip(int id){
		sum[id]=len[id]-sum[id];
		tag[id]^=1;
	}
	void down(int id){
		if(tag[id]){
			flip(lc);flip(rc);
			tag[id]=0;
		}
	}
	
	void flip(int a,int b,int l=1,int r=nn,int id=1){
		if(a>b) return ;
		if(l>=a and r<=b){
			flip(id);
			return ;
		}
		down(id);
		if(a<=mid) flip(a,b,l,mid,lc);
		if(b>mid) flip(a,b,mid+1,r,rc);
		up(id);
	}
	int ask(){
		return sum[1];
	}
	
};
int solve(){
	vector<int> pos;for(int i=0;i<all.size();i++) if(all[i]==1) pos.push_back(i);
	pos.push_back(all.size());all.clear();
	int lst=-1;m=0;
	for(int i=0;i<pos.size();i++){
		len[++m]=pos[i]-lst-1;
		lst=pos[i];
	}
	//cout<<m<<"asd\n";
	trcyx::build(1,nn,1);
	
	int s=0;m--;
	for(int i=1;i<=m;i++){
		s+=len[i];
		if(s%2==0) trcyx::flip(i,i);s++;
	}
//	cout<<trcyx::ask()<<"\n";
	int ans=0;
	for(int i=1;i<=m;i++) while(len[i]>(i>1)){
			ans+=trcyx::ask();
			trcyx::flip(i,m);
			len[i]--;
		}
		
	for(int i=1+m;i>=1;i--) while(len[i]>0){
			ans+=trcyx::ask();
			trcyx::flip(i,m);
			len[i]--;
		} 
	
	return ans;
}
signed main(){
	scanf("%s",str+1);n=strlen(str+1);
	int cnt1=0,lst=0,waste=0,cnt0=0;;
	for(int i=1;i<=n;i++) {
		if(str[i]=='1')
			lst++,cnt1++;
		if(str[i]=='0' or i==n){
			waste+=lst/2;lst%=2;
			if(lst) all.push_back(1);
			lst=0;
		}
		if(str[i]=='0') all.push_back(0),cnt0++;
	}
	if(!cnt1) return puts("0")*0;
	cout<<solve()+fullcombo(cnt1)+waste*cnt0<<"\n";
	return 0;
}