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;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-9;
//const ll MOD = 924844033;
const ld PI = 3.141592653589793;
const int maxn = 300001;
const ll MOD = 1e9 + 7;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../kolya_input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif


    function<void(int)> solve = [](int _) {
        string t;
        cin >> t;
        int n = t.size();

        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            if (t[i] == '1' && i % 2 == 0) {
                ++ans;
            }
        }

        const int cnt_zeros = count(t.begin(), t.end(), '0');
        if (cnt_zeros == n) {
            cout << 0;
            return;
        }
        auto process_ones = [&](int start_pos, int cnt, int suff_zeros) {
            const int pref_zeros = cnt_zeros - suff_zeros;
            ans += cnt_zeros * 1ll * (cnt / 2);
            if (cnt & 1) {
                if (start_pos % 2 == 0) {
                    ans += pref_zeros / 2;
                } else {
                    ans += (pref_zeros + 1) / 2;
                }
                ans += suff_zeros;
            }

        };
        int suff_zeros = 0;
        reverse(t.begin(), t.end());
        auto it = t.begin();
        while (it != t.end()) {
            auto one_pos = find(it, t.end(), '1');
            auto zero_pos = find(one_pos, t.end(), '0');
            int cnt = zero_pos - one_pos;
            suff_zeros += one_pos - it;
            process_ones(t.size() - 1 - (one_pos - t.begin()), cnt, suff_zeros);
            it = zero_pos;
        }
        t.erase(remove(t.begin(), t.end(), '0'), t.end());
        while (!t.empty()) {
            t.pop_back();
            ans += (t.size() + 1) / 2;
        }
        cout << ans;
    };


    fast_io();
    cout.precision(9);
    cout << fixed;
    auto start = chrono::steady_clock::now();
//    int t;
//    cin >> t;
    for (int i = 1; i <= 1; ++i)solve(i);
    auto end = chrono::steady_clock::now();

    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);

}
