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;
typedef long long ll;

// THINGS TO REMEMBER
// ENDL is slow, '\n' is fast
// Clear everything (including graphs) between test cases
// use anti-anti-hash: https://codeforces.com/blog/entry/62393
// pb-ds: https://codeforces.com/blog/entry/11080
// check when to use LLONG_MAX/LLONG_MIN vs INT_MAX or INT_MIN
// You frequently suffer from confirmation bias - you trust your initial solution and miss simple things. 
// When you hit a roadblock, remember to rethink the solution ground up, not just try hacky fixes

ll onePutter(ll oc){
	ll ans=0;
	for(ll i=1;i<=oc;i++){
		ans+=(i+1)/2;
	}
	return ans;
}


int main(){
	
	#ifndef ONLINE_JUDGE
    	freopen("input", "r", stdin);
    	freopen("output", "w", stdout);
    	freopen("error", "w", stderr);
	#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string t;
    cin>>t;

    // insert all 1s
    // insert 0s at even positions

    // each contiguous oneset can be in a high giving setting or a low giving setting
    // each zero inserted toggles the setting of everything after it

    // from left, if something is not in high, make it in high
    // else, don't do it now
    // then, from right, input all zeroes

    ll ans=0;

    // cerr<<"HI"
    // first, run length encode
    vector<ll> oneArr;
    vector<ll> zeroArr;

    ll n = t.length();

    ll i=0;

    ll oc=0;

    ll toAddOne=0;

    while(i<n){
    	int j=i+1;
    	while(j<n && t[j]==t[i]){
    		j++;
    	}
    	if(t[i]=='1'){
    		toAddOne+=((j-i)/2);
    		oneArr.push_back(j-i);
    		oc+=j-i;
    		if(zeroArr.empty())zeroArr.push_back(0);
    	}
    	else{
    		zeroArr.push_back(j-i);
    	}
    	i=j;
    }

    if(t[n-1]=='1')zeroArr.push_back(0);

    ll m=oneArr.size();

    // zeroArr[i] is the number of zeros before the oneset[i]
    // zeroArr[m] is the number of ones after

    ans+=onePutter(oc);

    vector<ll> config;

    // 1 is high, 2 is low, 0 is dontcare

    ll lefth=0,leftl=0,dc=0,righth=0,rightl=0;

    bool startsOdd = true;

    for(int i=0;i<m;i++){

    	if(oneArr[i]%2==0){
    		config.push_back(0);
    		dc++;
    	}
    	else{
	    	if(startsOdd){
	    		config.push_back(1);
	    		righth++;
	    	}    		
	    	else{
	    		config.push_back(2);
	    		rightl++;
	    	}
    	}

    	if(oneArr[i]%2==1){
    		startsOdd=!startsOdd;
    	}
    }

    // for(int i=0;i<m;i++){
    // 	cerr<<i<<" "<<config[i]<<" "<<oneArr[i]<<" "<<zeroArr[i]<<endl;
    // }
    // cerr<<zeroArr[m]<<endl;
    // cerr<<toAddOne<<endl;
    // cerr<<ans<<endl;
    // cerr<<leftl<<" "<<rightl<<" "<<lefth<<" "<<righth<<endl;

    bool toggled=false;

    for(int i=0;i<m;i++){
    	if(toggled){
    		if(config[i]==1)config[i]=2;
    		else if (config[i]==2)config[i]=1;
    	}

    	if(i==0 && zeroArr[i]==0){
    		// can't change the config of the first one
    		if(config[i]==1){
    			righth--;
    			lefth++;
    		}
    		else if (config[i]==2){
    			rightl--;
    			leftl++;
    		}
    		continue;
    	}

    	if(config[i]==2 || (config[i]==0 && (rightl>righth)) ) {
    		// toggle Yes -> insert 0
    		toggled=!toggled;
    		zeroArr[i]--;

    		ll temp = righth;
    		righth=rightl;
    		rightl=temp;

    		if(config[i]==2){
	    		righth--;
	    		lefth++;    			
	    		config[i]=1;
    		}

    		ans+=toAddOne+lefth+righth;
    	}
    	else{
    		if(config[i]==1){
    			righth--;
    			lefth++;
    		}
    	}
    	// cerr<<i<<" "<<ans<<endl;
    	// cerr<<i<<" "<<leftl<<" "<<rightl<<" "<<lefth<<" "<<righth<<endl;
    }

    for(int i=m;i>=0;i--){
    	// cerr<<i<<" "<<leftl<<" "<<rightl<<" "<<lefth<<" "<<righth<<endl;
    	// if(i<m)cerr<<config[i]<<endl;
    	while(zeroArr[i]>0){
    		ll temp = righth;
    		righth=rightl;
    		rightl=temp;

    		// cerr<<i<<" "<<lefth<<" "<<righth<<endl;

    		ans+=toAddOne+lefth+righth;

    		zeroArr[i]--;
    	}
    	if(i==0)break;
    	if(config[i-1]==1){
    		lefth--;
    		righth++;
    	}
    	else if (config[i-1]==2){
    		leftl--;
    		rightl++;
    	}
    }

    cout<<ans<<endl;
    // cerr<<ans<<" "<<lefth<<" "<<leftl<<" "<<righth<<" "<<rightl<<endl;


}