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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
char p[201000];
int n, C[2], v[201000], S[201000];
long long s=0;
int main(){
    int i;
    scanf("%s",p);
    for(i=0;p[i];i++){
        C[p[i]-'0']++;
    }
    n=i;
    for(i=1;i<=C[1];i++){
        s += (i+1)/2;
    }
    int c=0, t=0;
    for(i=0;p[i];i++){
        if(p[i]=='1')c++;
        if(p[i]=='0' && c%2==1){
            c++;
            t++;
            s+=(C[1]+t+1)/2;
            v[i]=1;
        }
        S[i] = (c+1)/2;
    }
    int c0=0,c1=0;
    for(i=n-1;i>=0;i--){
        swap(c0,c1);
        if(p[i]=='0'){
            if(!v[i]){
                s+=c1+S[i];
            }
        }
        if(p[i]=='1')c1++;
        
    }
    printf("%lld\n",s);
}
