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;

const int INF = 88888888;
const int N = 2502;

typedef vector<vector<int> > vvi;
typedef vector<int> vi;

#define all(x) (x).begin(), (x).end()

long long ans = 0;

int main()
{
    string s;
    cin >> s;
    long long cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '1') cnt1++;
        else cnt0++;
    }
    for (int j = 1; j <= cnt1; j++)
    {
        ans += (j + 1) / 2;
    }
    string s2 = "";
    for (int i = 0; i < s.size(); )
    {
        int j = i;
        while (j < s.size() && s[j] == s[i])
        {
            j++;
        }
        int cnt = j - i;
        if (s[i] == '0')
        {
            for (int j = 0; j < cnt; j++) s2 += "0";
        }
        else
        {
            for (int j = 0; j < cnt % 2; j++) s2 += "1";
            ans += 1ll * cnt0 * (cnt / 2);
        }
        i = j;
    }
    int z = 0, d = 0;
    for (int i = 0; i < s2.size(); i++)
    {
        if (s2[i] == '1')
        {
            if (d % 2 == 0) ans += (z / 2) + (cnt0 - z);
            else ans += ((z + 1) / 2) + cnt0 - z;
            d ^= 1;
        }
        else
        {
            z++;
        }
    }
    cout << ans;
}
