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 rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
  string T; cin >> T;
  int N = T.size();
  vector<bool> A(N);
  rep(i, N) A[i] = (T[i] == '1');

  vector<vector<int>> r(2, vector<int>(N + 1, 0));
  for (int i = N - 1; i >= 0; i--) {
    r[0][i] = r[0][i + 1];
    r[1][i] = r[1][i + 1];
    if (A[i]) r[i % 2][i]++;
  }

  int now = 0, t = N, s = 0, p = 0;
  long long ans = r[0][0];
  bool check = false;
  while (t > 0) {
    if (check) {
      ans += t / 2;
      t--;
    } else {
      for (; now < N; now++) {
        if (now % 2 == p) {
          if (A[now]) s++;
          else break;
        }
      }
      if (now >= N) {
        check = true;
        continue;
      }
      now++;
      t--;
      p ^= 1;
      ans += s + r[p][now];
    }
  }

  cout << ans << endl;
}

