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>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;

string T;
const int maxn = 2e5 + 5;
int suf[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    int n = T.length();
    int cnt = 0;
    for(int i = 0;i < n;i++){
        cnt += (T[i] == '1');
    }
    ll ans = 0;
    for(int i = 1; i <= cnt;i++){
        ans += (i + 1) / 2;
    }
    int zero = n - cnt;
    cnt = 0;
    vector<int> v;
    for(int i = 0;i < n;i++){
        if(T[i] == '1'){
            cnt++;
        }else{
            ans += 1LL * cnt / 2 * zero;
            if(cnt & 1){
                v.push_back(1);
            }
            cnt = 0;
            v.push_back(0);
        }
    }
    ans += 1LL * cnt / 2 * zero;
    if(cnt & 1){
        v.push_back(1);
    }
    int m = v.size();
    suf[m] = 0;
    for(int i = m - 1;i >= 0;i--){
        suf[i] = suf[i + 1] + (v[i] == 0);
    }
    cnt = 0;
    for(int i = 0;i < m;i++){
        if(v[i] == 1){
            if(i & 1){
                ans += cnt / 2 + suf[i + 1];
            }else{
                ans += (cnt + 1) / 2 + suf[i + 1];
            }
        }else{
            cnt++;
        }
    }
    cout << ans << endl;
    return 0;
}
