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>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll Tn;
char T[202020];
deque<ll> dqe;

ll i, j, k;
ll ans;

int main(){
    scanf("%s", T);
    Tn = strlen(T);
    ll a = 0, b = 0, c = 0;

    fornum(i,0,Tn){
        if(T[i]=='1'){
            if(i%2==0)
                ++a;
            else
                ++b;
        }
    }
    j = 1;
    string s;
    fornum(i,0,Tn){
        if(T[i]=='1'){
            if(j==1){
                --a;
                ++c;
            }else{
                --b;
            }
            j ^= 1;
            s += '1';
        }else{
            if(j==0){
                s += '0';
                j = 1;
            }else{
                ans += c + a;
                swap(a, b);
            }
        }
    }
    //printf("%lld,%lld,%lld\n", a, b, c);
    if(c==0){
        printf("0\n");
        return 0;
    }
    i = s.size();
    while(i>0){
        --i;
        if(s[i]=='1'){
            if(i%2==0){
                ++a;
                --c;
            }else{
                ++b;
            }
        }else{
            ans += a + c;
            swap(a, b);
        }
    }
    c = a + b;
    while(c>0){
        ans += (c + 1) / 2;
        --c;
    }
    printf("%lld\n", ans);

    return 0;
}