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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  string T;
  cin>>T;
  int N=T.size();

  ll one=0;
  rep(i,N) if(T[i]=='1') one++;

  ll ans=0;
  if(one%2) ans=(one/2)*((one/2)+1)+(one+1)/2;
  else ans=(one/2)*((one/2)+1);

  ll rest=N-one;
  vector<int> A;
  A.push_back(0);
  ll tmp=0;
  for(int i=0;i<N;i++){
    if(tmp==0){
      if(T[i]=='1') tmp++;
      else A[A.size()-1]++;
    }else{
      if(T[i]=='1') tmp++;
      else{
        if(tmp%2) A.push_back(1);
        else A[A.size()-1]++;
        ans+=(tmp/2)*rest;
        tmp=0;
      }
    }
  }
  if(tmp>0){
    if(tmp%2) A.push_back(0);
    ans+=(tmp/2)*rest;
  }

  int K=A.size();
  ll res=0;
  vector<ll> sum(K+1,0);
  for(int i=0;i<K;i++) sum[i+1]=sum[i]+A[i];
  for(int i=0;i+1<K;i++){
    if((sum[i+1]+i+1)%2) res+=(sum[i+1]+1)/2;
    else res+=(sum[i+1])/2;
  }
  for(int i=0;i+1<K;i++){
    res+=sum[K]-sum[i+1];
  }
  ans+=res;
  cout<<ans<<endl;


  return 0;
}
