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;
const int MAX_N=5+2e5;
struct SEG{
	struct Node{
		int k[2]; bool tag;
	}t[MAX_N<<2];
	inline void put_tag(int x,bool tag){
		if(!tag) return;
		swap(t[x].k[0],t[x].k[1]);
		t[x].tag^=1;
	}
	inline void down(int x){
		put_tag(x+x,t[x].tag);
		put_tag(x+x+1,t[x].tag);
		t[x].tag=0;
	}
	inline void up(int x){
		t[x].k[0]=t[x+x].k[0]+t[x+x+1].k[0];
		t[x].k[1]=t[x+x].k[1]+t[x+x+1].k[1];
	}
	void init(string& s,int p,int l,int r){
		if(l==r){
			t[p].k[0]=t[p].k[1]=t[p].tag=0;
			if(s[l]=='1')
				t[p].k[~l&1]=1;
			return;
		}
		int m=l+r>>1;
		init(s,p+p,l,m);
		init(s,p+p+1,m+1,r);
		up(p);
	}
	void change(int p,int l,int r,int x,int y,bool tag){
		if(y<l||r<x) return;
		if(x<=l&&r<=y) return put_tag(p,tag);
		int m=l+r>>1; down(p);
		change(p+p,l,m,x,y,tag);
		change(p+p+1,m+1,r,x,y,tag);
		up(p);
	}
	int query(int p,int l,int r,int x,int y){
		if(y<l||r<x) return 0;
		if(x<=l&&r<=y) return t[p].k[1];
		int m=l+r>>1; down(p);
		return query(p+p,l,m,x,y)+query(p+p+1,m+1,r,x,y);
	}
}seg;
int tran(string& s,string& s1,char c='\n'){
	s1.clear();
	int ret=0;
	for(int i=0;i<s.length();++i){
		if(s[i]=='1'){
			int j=i;
			while(s[j]=='1'&&s[j+1]=='1')
				j+=2;
			ret+=j-i;
			if(s[j]=='0') i=j-1;
			else{
				s1.push_back(s[j]);
				i=j;
			}
		}else{
			s1.push_back(s[i]);
		}
	}
	return ret;
}
bool vis[MAX_N];
int main(){
	int c1=0;
	string s,s1; cin>>s;
	c1=tran(s,s1,'1');
	int tp=(int)s1.length();
	seg.init(s1,1,0,tp-1);
//	cout<<s1<<endl;
	long long ans=c1/2+seg.query(1,0,tp-1,0,tp-1);
//	printf("[%lld]",ans);
	for(int i=0;i<s1.length();++i){
		if(s1[i]=='1'){
			if(seg.query(1,0,tp-1,i,i)==0){
				assert(vis[i-1]==0);
				vis[i-1]=1;
				seg.change(1,0,tp-1,i,tp-1,true);
				ans+=c1/2+seg.query(1,0,tp-1,0,tp-1);
//				printf("[%lld]",ans);
			}
		}
	}
	for(int i=(int)s1.length()-1;i>=0;--i)
		if(s1[i]=='0'&&!vis[i]){
			vis[i]=1;
			seg.change(1,0,tp-1,i,tp-1,true);
			ans+=c1/2+seg.query(1,0,tp-1,0,tp-1);
		}
	int c2=c1;
	for(int i=0;i<s1.length();++i) 
		if(s1[i]=='1') ++c2;
	while(c2>0){
		c2--;
		ans+=(c2+1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}