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;

char s[200010];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int c0 = 0, c1 = 0;
    for (int i = 1; i <= n; ++i)
        c0 += s[i] == '0', c1 += s[i] == '1';
    ll ans = 0;
    for (int i = 1; i < c1; ++i)
        ans += (i + 1) / 2;
    int cur = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') {
            ++cur;
            continue;
        }
        if (s[i] == s[i + 1]) {
            ++i;
            ans += c0 + 1;
            continue;
        }
        int ruc = c0 - cur;
        if (i & 1) ans += 1 + ruc + cur / 2;
        else ans += ruc + (cur - 1) / 2 + 1;
    }
    cout << ans << '\n';
    return 0;
}