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 sz(x) (int)x.size()
#define ld long double
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

const int INF = 1e8;

ll res = 0, rem = 0, oc = 0;
string s, nxt = "";
//before parity, after parity
int b0 = 0;
vector<int> ap(2, 0);
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> s;
    string t = "", tr = "";
    for(int i = 0;  i < sz(s); ++i){
        if(s[i] == '0'){
            tr += '0';
            continue;
        }
        while(i < sz(s) && s[i] == '1') t += '1', i++;
        if(sz(t)%2) tr += '1';
        oc += sz(t)/2 * 2;
        t = "";
        i--;
    }
    s = tr;
    // cout << s << " " << oc << "\n";
    //add for every one of even position (ap.f)
    for(int i = 0; i < sz(s); ++i){
        if(s[i] == '1'){
            ap[0] += i%2 == 0;
            ap[1] += i%2 == 1;
        }
    }
    for(int i = 0; i < sz(s); ++i){
        if(!sz(t) && s[i] == '0'){
            if(i%2) res += ap[1];
            else res += ap[0];
            res += oc/2;
        }
        else t += s[i];
    }
    // s is s without beginning 0s
    s = t;
    ap[0] = ap[1] = 0;
    for(int i = 0; i < sz(s); ++i){
        if(s[i] == '1'){
            ap[0] += i%2 == 0;
            ap[1] += i%2 == 1;
        }
    }
    // cout << ap[0] << " " << ap[1] << "\n";
    for(int i = 0; i < sz(s); ++i){
        // cout << s[i] << " " << res << "\n";
        if(s[i] == '0'){
            if(i + 1 < sz(s)){
                if(s[i + 1] == '0'){
                    int ppos = (i - rem + INF)%2;
                    if(ppos != i%2) res += ap[1];
                    else res += ap[0];
                    res += b0 + oc/2;
                    rem++;
                }
                else nxt += '0';
            }
            else{
                nxt += '0';
                continue;
            }
        }
        else{
            nxt += '1';
            if(sz(nxt)%2 == 1) b0++;
            if(i%2) ap[1]--;
            else ap[0]--;
        }
    }
    // cout << nxt << " " << res << "\n";
    b0 = ap[0] = ap[1] = rem = 0;
    for(int i = 0; i < sz(nxt); ++i){
        if(nxt[i] == '1' && i%2 == 0) b0++;
    }
    string rr = "";
    for(int i = sz(nxt) - 1; i >= 0; --i){
        if(nxt[i] == '0'){
            res += b0;
            if(i%2) res += (sz(rr) + 1)/2;
            else res += sz(rr)/2;
            res += oc/2;
        }
        else{
            rr += '1';
            if(i%2 == 0) b0--;         
        }
        // cout << nxt[i] << " " << res << "\n";
    }
    oc += sz(rr);
    // cout << res << " " << rr << "\n";
    if(oc%2) res += (oc/2 + 1), oc--;
    res += ((oc/2) * (oc/2 + 1));
    cout << res;
    return 0;
}