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 <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string T; cin >> T;
    vector<int> s;
    vector<int> pos;
    int ones = 0;
    for(int i=0;i<T.size();i++){
        if(T[i] == '0'){
            if(ones > 0 && ones%2 == 1){
                s.push_back(i);
            } else {
                pos.push_back(i);
            }
            ones = 0;
        } else {
            s.push_back(i);
            ++ones;
        }
    }
    int turn = s.size();
    long long res = 0;
    while(!pos.empty()){
        int b = pos.back(); pos.pop_back();
        int idx = s.size() - 1;
        while(idx >= 0 && b < s[idx]){
            int p = s[idx];
            int v = T[p] - '0';
            if(idx%2 == 0) res += v * (turn - idx);
            res += (T.size() - turn + idx%2) / 2 * v;
            s.pop_back();
            --idx;
        }
        ++turn;
    }
    for(int i=0;i<s.size();i+=2){
        res += (T.size()-i) * (T[i]-'0');
    }
    cout << res << endl;
}