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 fi first
#define se second

const int N = 100100;

using namespace std;

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        string s;
        cin >> s;

        long long res = 0, A = 0, B = 0, C = 0;
        vector < int > a, v;
        for(int i = 0; i < s.size(); i++){
                if(!v.empty() && v.back() == 1 && s[i] == '1'){
                        v.pop_back();
                        C += 1;
                } else{
                        v.push_back(s[i] - '0');
                }
                if(i % 2 == 0){
                        res += s[i] - '0';
                }
                A += s[i] - '0';
                B += 1 - (s[i] - '0');
        }
        for(int i = 1; i < A; i++){
                res += (i + 1) / 2;
        }

        res += 1ll * C * B;

        a.push_back(0);
        for(int x: v){
                if(x == 0){
                        a.back() += 1;
                } else{
                        a.push_back(0);
                }
        }
        int m = a.size() - 1;
        long long S = a[0];
        for(int i = 1; i <= m; i++){
                if((S + i) % 2){
                        res += S / 2;
                } else{
                        res += (S + 1) / 2;
                }
                res += 1ll * i * a[i];
                S += a[i];
        }

        cout << res << "\n";
}
