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;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (int)2e5 + 10;
char inp[N];

int main(){
  fastIO;
  string t;
  cin >> t;
  int n = t.size();
  int zer = 0, one = 0;
  for(int i = 0 ; i < n; i ++ ){
    inp[i]=t[i];
    if(t[i]=='0')zer++;
    else one++;
  }
  vector<int> rem;
  int pf = 0;
  ll ans = 0;
  for(int i = 0 ; i < n ; i ++ ){
    if(t[i]=='0'){
      rem.push_back(0);
    }
    else{
      if(!rem.empty() && rem.back() == 1){
        rem.pop_back();
        ans += zer;
        continue;
      }
      rem.push_back(1);
    }
  }
  pf = 0;
  int xr = 1;
  for(auto x : rem){
    if(x==0) pf ++ ;
    else{
      ans += (pf+xr)/2;
      ans += zer-pf;
    }
    xr ^= 1;
  }
  for(int i = 1; i <= one; i ++ ){
    ans += (i + 1) / 2;
  }
  cout << ans << "\n";
  return 0;
}