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 MOD 1000000007
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}


long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if ((j & 1LL)){
				res *= i;
				if (res >= MOD){
					res %= MOD;
				}
			}
			j >>= 1;
			i *= i;
			if (i >= MOD){
				i %= MOD;
			}
		}
		return res;
	}
class Combination{
	
public:
	vector<long long int> k;
	vector<long long int> r;
	void resize(int N){
		k.resize(N + 2);
		r.resize(N + 2);
		k[0] = 1;
		for (int i = 1; i < N+2; i++){
			k[i] = k[i - 1];
			k[i] *= i;
			if (k[i] >= MOD)k[i] %= MOD;
		}
		long long int al = k[k.size() - 1];
		long long int iv = ppow(k[k.size() - 1],MOD-2);
		r[k.size() - 1] = iv;
		for (int i = (int)(r.size()) - 2; i >= 0; i--){
			r[i] = r[i + 1] * (i + 1);
			if (r[i] >= MOD){
				r[i] %= MOD;
			}
		}
	}
	long long int C(int a, int b){
		if (a < b)return 0;
		long long int up = k[a];
		long long int dw = r[b] * r[a - b];
		dw %= MOD;
		up *= dw;
		up %= MOD;
		return up;
	}
	long long int H(int a, int b){
		return C(a + b - 1, b);
	}
	long long int catalan_number(int n){
		return (C(2 * n, n) + MOD - C(2 * n, n - 1)) % MOD;
	}
};
Combination C;

#define MAX 200002

int calc_score(string a){
	int num=0;
	for(int i=0;i<a.size();i+=2){
		num+=a[i]-'0';
	}
	return num;
}

map<string,int> dp;

inline int dfs(string a){
	if(dp.count(a))return dp[a];
	int sc=calc_score(a);
	if(a.size()==1)return sc;
	string s=a;
	int mx=0;
	string ww;
	if(true){
		for(int i=0;i<s.size();i++){
			string t=s.substr(0,i)+s.substr(i+1,s.size()-i-1);
			int z=dfs(t);
			if(mx<z){
				mx=z;
				ww=t;
			}
		}
		
		int scc=-1;
		string nex;
		for(int i=0;i<s.size();i++){
			string t=s.substr(0,i)+s.substr(i+1,s.size()-i-1);
			int z=calc_score(t);
			if(i%2==0&&s[i]=='0'){
				scc=z;
				nex=t;
				break;
			}
		}
		if(nex.size()==0){
			nex=s;
			nex.pop_back();
		}
		if(mx!=dfs(nex)){
			cout<<s<<" "<<nex<<" but "<<ww<<" "<<dfs(nex)<<" "<<dfs(ww)<<" "<<calc_score(nex)<<" "<<calc_score(ww)<<endl;
		}
	}
	//cerr<<a<<" -> "<<ww<<endl;
	sc+=mx;
	dp[a]=sc;
	return sc;
}




inline int test(string a){
	int u1=dfs(a);//cerr<<dfs(a)<<endl;
	int ans=calc_score(a);
	string s=a;
	while(s.size()>1){
		string nex;
		int sc=-1;
		for(int i=0;i<s.size();i++){
			string t=s.substr(0,i)+s.substr(i+1,s.size()-i-1);
			int z=calc_score(t);
			if(sc<z){
				sc=z;
				nex=t;
			}
		}
		ans+=sc;
		s=nex;
	}
	//cerr<<ans<<endl;
	int u2=ans;
	if(u1!=u2){
		//cerr<<"e"<<endl;
		//cerr<<u1<<" "<<u2<<" "<<a<<endl;
		//exit(0);
	}
}

char buf[MAX];
string s;


struct st{
	int one;
	int zero;
	st(){
		one=0;
		zero=0;
	}
};

st merge(st a,st b){
	st r;
	r.one=a.one+b.one;
	r.zero=a.zero+b.zero;
}

#define MAX 200002
st seg[MAX*4];
inline void init(int b,int l,int r){
	if(l+1==r){
		if(s[l]=='1'){
			seg[b].one=1;
		}
		else{
			seg[b].zero=1;
		}
		return;
	}
	init(b*2+1,l,(l+r)>>1);
	init(b*2+2,(l+r)>>1,r);
	seg[b]=merge(seg[b*2+1],seg[b*2+2]);
}
vector<int> zero[2];
vector<int> one[2];


int main(){
	//string g;
	//cin>>g;
	//cout<<test(g)<<endl;
	const int dd=17;
	//for(int i=0;i<(1<<dd);i++){
	/*string d;
		for(int j=0;j<dd;j++){
			if(((i>>j))&1){
				d.push_back('0');
			}
			else{
				d.push_back('1');
			}
		}
		test(d);
	}
	*/
	scanf("%s",buf);
	s=buf;
	for(int i=0;i<s.size();i++){
		if(s[i]=='0'){
			zero[i&1].push_back(i);
		}
		else{
			one[i&1].push_back(i);
		}
	}
	int pos=0;
	bool flag=false;
	string ret;
	long long int ans=calc_score(s);
	long long int tmp=0;
	while(true){
		int id=lower_bound(zero[flag].begin(),zero[flag].end(),pos)-zero[flag].begin();
		if(id==zero[flag].size())break;
		for(int i=pos;i<zero[flag][id];i++){
			ret.push_back(s[i]);
			if(ret.size()%2&&s[i]=='1'){
				tmp++;
			}
		}
		pos=zero[flag][id]+1;
		flag^=true;
		long long int g=tmp;
		if(true){
			int id=lower_bound(one[flag].begin(),one[flag].end(),pos)-one[flag].begin();
			g+=one[flag].size()-id;
		}
		ans+=g;
		//cerr<<"turn "<<g<<" "<<pos<<endl;
	}
	int n=s.size();
	for(int i=pos;i<n;i++){
		ret.push_back(s[i]);
			if(ret.size()%2&&s[i]=='1'){
				tmp++;
			}
	}
	s=ret;
	while(s.size()){
		if(s.size()%2&&s.back()=='1')tmp--;
		s.pop_back();
		ans+=tmp;
		//cerr<<s<<" "<<tmp<<endl;
	}
	printf("%lld\n",ans);
	
	return 0;
}

