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;

const int N=200000;

char s[N+9];
int n;

void into(){
  scanf("%s",s+1);
  n=strlen(s+1);
}

int pre[N+9],suf[N+9];
LL ans;

void Get_ans(){
  int cnt=0;
  for (int i=1;i<=n;++i) pre[i]=pre[i-1]+(s[i]=='0');
  for (int i=n;i>=1;--i) suf[i]=suf[i+1]+(s[i]=='0');
  int flag=1;
  for (int i=1;i<=n;++i)
	if (s[i]=='1'){
	  ans+=(pre[i]+1+(i&1)>>1)+(flag?suf[i]:0);
	  flag^=1;
	}else flag=1;
  for (int i=1;i<n-pre[n];++i) ans+=n-pre[n]-i+1>>1;
}

void work(){
  Get_ans();
}

void outo(){
  printf("%lld\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}