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<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu) FUNC(printe) FUNC(printe0);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    string t; cin >> t;
    int n = t.size();
    vector<int> accs(n + 2);
    for(int i = n - 1; i >= 0; i--){
        accs[i] = accs[i + 2] + (t[i] == '1');
    }
    ll ans = 0;
    int idx = 0;
    // int size = n;
    for(int i = 0; i < n; i++){
        ans += accs[idx];
        bool done = false;
        while(idx < (int)t.size()){
            if(t[idx] - '0' == 0){
                idx++;
                // size--;
                done = true;
                break;
            }
            // ans += (size - 1) - idx;
            ans += (t.size() - 1) - idx;
            idx += 2;
        }
        if(!done){
            t.pop_back();
        }
    }
    cout << ans << '\n';
}
