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 <cstring>
#include <vector>

using namespace std;

char t[200001];

int main() {
    int n, m, c0 = 0, c1 = 0, c = 0, x = 0, i, j;
    long long ans = 0;
    vector<int> v;
    
    scanf("%s", t);
    
    n = strlen(t);
    
    for (i = 0; i < n; i++) {
        if (t[i] == '0') {
            c0++;
        } else {
            c1++;
            ans += (c1 + 1) / 2;
        }
    }
    
    if (c0 == 0) {
        printf("%lld\n", ans);
        
        return 0;
    }
    
    for (i = 0; i < n; ) {
        for (j = i; j < n; j++) {
            if (t[i] != t[j]) break;
        }
        
        if (t[i] == '0') {
            c += j - i;
        } else {
            int x = j - i;
            
            ans += (long long)c0 * (x / 2);
            
            if (x % 2 == 1) {
                v.push_back(c);
                c = 0;
            }
        }
        
        i = j;
    }
    
    v.push_back(c);
    
    m = v.size();
    
    for (i = 1; i < m; i++) {
        if (v[i] > 0) {
            v[i]--;
            ans += i + (m - i) / 2;
        }
    }
    
    for (i = 0; i < m; i++) {
        while (v[i] >= 2) {
            v[i] -= 2;
            ans += i * 2 + m - i - 1;
        }
    }
    
    for (i = m - 1; i >= 0; i--) {
        if (v[i] > 0) {
            x = m - i - 1 - x;
            ans += m - x - 1;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}
