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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

int main(){
  string s;
  cin >> s;
  int cnt_one = 0;
  vector<int> pos_zero;
  rep(i, s.size()) {
    if (s[i] == '1') {
      cnt_one++;
    } else {
      pos_zero.push_back(cnt_one);
    }
  }

  ll ans = 0;
  for (int i = 1; i <= cnt_one; ++i) {
    ans += (i + 1) / 2;
  }

  vector<int> used(pos_zero.size(), -1);
  int cnt_used_zero = 0;
  rep(i, pos_zero.size()) {
    pos_zero[i] += cnt_used_zero;
    if (pos_zero[i] % 2 == 1) {
      used[i] = cnt_used_zero;
      cnt_used_zero++;
      ans += (cnt_one + cnt_used_zero + 1) / 2;
    }
  }

  int rev_cnt_zero = 0;
  int odd_pos = 0;
  int even_pos = 0;
  rrep(i, pos_zero.size()) {
    if (used[i] < 0) {
      rev_cnt_zero++;
      int len = (cnt_one + cnt_used_zero + rev_cnt_zero);
      swap(odd_pos, even_pos);
      odd_pos++;
      ans += (len + 1) / 2 - odd_pos;
    } else {
      even_pos++;
    }
  }
      
  cout << ans << endl;
}
