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 <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int main(void){
    string T;
    cin >> T;
    ll ans=T.size();
    if(ans&1) ans=(ans+1)*(ans+1)/4;
    else ans=ans*ans/4+ans/2;
    int r=1;
    vector<ll> v{0};
    for(int i=0; i<T.size(); ++i){
        if(T[i]=='0'){
            if(i%2==r) ++v.back();
            else{
                v.emplace_back(1);
                r=1-r;
            }
        }
    }
    for(int i=0; i<v.size(); ++i) ans -= v[i]*((i+1)/2);
    cout << ans << endl;
    return 0;
}
