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<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
#include<numeric>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int ans;

int main(){
    string t;
    cin >> t;
    Int n = t.size();
    string comp = "";
    Int all_cnt[2] = {0,0};
    Int always = 0;
    for(char c:t){
        all_cnt[c - '0']++;
        if(!comp.empty() && comp.back() == '1' && c == '1'){
            comp.pop_back();
            always++;
        }
        else comp.push_back(c);
    }
    
    ans += (all_cnt[1] / 2) * (all_cnt[1] / 2 + 1);
    if(all_cnt[1] % 2)ans += all_cnt[1] / 2 + 1;
    ans += always * all_cnt[0];
    Int zero = 0;
    Int one = 0;
    for(char c: comp){
        if(c == '0')zero++;
        else{
            one++;
            Int from = one + zero;
            Int to = one;to;
            ans += all_cnt[0];
            ans -= (from / 2) - (to/2);
        }
    }
    cout << ans << endl;
        
    return 0;
}