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>
#include <math.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define PI 3.14159265359
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  string t;
  cin >> t;
  int zero = 0;

  ll ans = 0;
  rep(i, t.size()) {
    if (t[i]-'0' == 0) zero++;
    else if (i % 2 == 0) {
      ans += (zero + 1) / 2;
    } else {
      ans += zero / 2;
    }
  }

  zero = 0;
  ll one = 0;
  bool ris1 = false;
  for (int i=t.size()-1; i>=0; i--) {
    if (t[i]-'0' == 1) one++;
    if (t[i]-'0' == 0) {
      zero++;
      ris1 = false;
    } else if (!ris1) {
      ans += zero; ris1 = true;
    } else {
      ris1 = false;
    }
  }

  //cout << "the number of 1 is " << one << endl;
  ans += (one + 1) / 2 * ((one + 1) / 2 + 1);
  ans = ans - (one % 2 == 0 ? 0 : (one + 1) / 2);

  cout << ans << endl;

  return 0;
}

/*
*/
