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 forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int n = si(s);
    ll ans = 0;
    {
        vector<char> ns;
        for (auto c : s) {
            if (c == '1' && !ns.empty() && ns.back() == '1') {
                ns.pop_back();
                ans += n;
                n -= 2;
            }
            else ns.push_back(c);
        }
        s = "";
        for (auto c : ns) s += c;
    }
    ll zeros = 0;
    n = si(s);
    dforsn(i,0,n) {
        if (s[i] == '1') {
            ans += (i+2)/2;
            ans += zeros;
        }
        else zeros++;
    }
    cout << ans;

    return 0;
}
