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;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int INF = 1e18;

const int N = 5e5 + 7;
ii mx[N << 2], mn[N << 2];
ii prop[N << 2];


ii getmax(ii a, ii b) {
    if (a.f > b.f || (a.f == b.f && a.s < b.s))
        return a;
    else
        return b;
}
ii getmin(ii a, ii b) {
    return min(a, b);    
}

void relax(int v) {
    mx[v] = getmax(mx[v * 2 + 1], mx[v * 2 + 2]);
    mn[v] = getmin(mn[v * 2 + 1], mn[v * 2 + 2]);
}   
void build(int v, int tl, int tr, vector <int> &a) {
    if (tl == tr) {
        if (a[tl] == -INF) {
            mx[v] = mp(-INF, -INF);
            mn[v] = mp(INF, INF);
        }   
        else {
            mx[v] = mn[v] = mp(a[tl], tl);
        }
        return;
    }   
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm, a);
    build(v * 2 + 2, tm + 1, tr, a);
    relax(v);
}
void gap(int v, ii e) {
    if (mx[v].f != -INF) {
        mx[v].f = mx[v].f * e.f + e.s;        
    }   
    if (mn[v].f != INF) {
        mn[v].f = mn[v].f * e.f + e.s;
    }   
    if (mx[v].f != -INF && mx[v] < mn[v]) {
        swap(mx[v], mn[v]);
    }   
    prop[v].f *= e.f;
    prop[v].s = prop[v].s * e.f + e.s;
}
void push(int v) {
    gap(v * 2 + 1, prop[v]);
    gap(v * 2 + 2, prop[v]);
    prop[v] = mp(1, 0);       
}   
void del(int v, int tl, int tr, int i) {
    if (tl == tr) {
        mx[v] = mp(-INF, -INF);
        mn[v] = mp(INF, INF);
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    if (i <= tm)
        del(v * 2 + 1, tl, tm, i);
    else
        del(v * 2 + 2, tm + 1, tr, i);


    relax(v);

    //cout << "del " << v << ' ' << tl << ' ' << tr << " : " << mx[v].f << ' ' << mx[v].s << endl;

}
void upd(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl)
        return;
    if (l <= tl && tr <= r) {
        gap(v, mp(1, x));
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    upd(v * 2 + 1, tl, tm, l, r, x);
    upd(v * 2 + 2, tm + 1, tr, l, r, x);
    relax(v);
}
void fac(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return;
    if (l <= tl && tr <= r) {
        gap(v, mp(-1, 0));
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    fac(v * 2 + 1, tl, tm, l, r);
    fac(v * 2 + 2, tm + 1, tr, l, r);
    relax(v);        
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < (N << 2); ++i)
        prop[i] = mp(1, 0);

    string t;
    cin >> t;

    string s = t;

    int n = t.size();

    int c0 = 0, c1 = 0;
    for (char c : t) {
        if (c == '0')
            ++c0;
        else
            ++c1;
    }   

    vector <bool> used(n);
    int ans = 0;
    for (int i = 1; i <= c1; ++i)
        ans += (i + 1) / 2;

    for (int i = 0; i < n; ++i)
        if (s[i] == '1')
            used[i] = 1;

    vector <int> pos(n);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        pos[i] = cur;
        cur += used[i];
    }
    vector <int> sc(n, -INF);
    int b = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '1') {
            if (pos[i] & 1)
                ++b;
            else
                --b;
        }   
        else if (!used[i]) {
            sc[i] = b;
        }   
    }
    
    int x = 0;
    for (int i = 0; i < n; ++i)
        if (s[i] == '1' && pos[i] % 2 == 0)
            ++x;

    build(0, 0, n - 1, sc);
    for (int add = 0; add < c0; ++add) {
        auto best = mx[0];
        int i = best.s;
        x += best.f;
        ans += x;

        //cout << "best " << best.f << ' ' << best.s << endl;
        //cout << "add " << x << endl;

        del(0, 0, n - 1, i);
        fac(0, 0, n - 1, i + 1, n - 1);

        //cout << "fac : " << mx[0].f << ' ' << mx[0].s << endl;

        upd(0, 0, n - 1, 0, i - 1, -2 * best.f);        

        //cout << "delta " << -2 * best.f << endl;
        //cout << "upd : " << mx[0].f << ' ' << mx[0].s << endl;
    }   
    cout << ans << endl;
}