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>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat May 30 22:45:01 JST 2020
 **/

template <class T> std::vector<std::pair<T, int>> run_length_encode(const std::vector<T>& a) {
    std::vector<std::pair<T, int>> ret;
    int cur = 0;
    for (int i = 0; i < a.size(); i++) {
        cur++;
        if (i == a.size() - 1 || a[i] != a[i + 1]) {
            ret.emplace_back(a[i], cur);
            cur = 0;
        }
    }
    return ret;
}
std::vector<std::pair<char, int>> run_length_encode(const std::string& a) {
    std::vector<std::pair<char, int>> ret;
    int cur = 0;
    for (int i = 0; i < a.size(); i++) {
        cur++;
        if (i == a.size() - 1 || a[i] != a[i + 1]) {
            ret.emplace_back(a[i], cur);
            cur = 0;
        }
    }
    return ret;
}

signed main() {
    std::vector<int> a = {2, 2};
    std::string t;
    std::cin >> t;
    auto ps = run_length_encode(t);
    dump(ps);
    Int rem = 0, cur_zero = 0;
    std::vector<Int> zeros;
    for (auto& p : ps) {
        if (p.first == '0') {
            cur_zero += p.second;
        } else {
            rem += p.second / 2;
            if (p.second % 2) {
                zeros.push_back(cur_zero);
                cur_zero = 0;
            }
        }
    }
    zeros.push_back(cur_zero);
    Int one = std::count(t.begin(), t.end(), '1');
    Int zero = t.size() - one;
    // 全部1になってから
    Int ans = (one / 2) * (one / 2 + 1);
    if (one % 2) ans += (one + 1) / 2;
    // rem
    ans += rem * zero;
    // その他
    REP(i, zeros.size()) {
        ans += i * zeros[i];
    }
    Int acc = 0;
    REP(i, zeros.size() - 1) {
        acc += zeros[i];
        ans += (acc + i % 2) / 2;
    }
    std::cout << ans << std::endl;
}
