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;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  vector<pair<int, int>> range;
  range.reserve(n);
  for (int i = 0, cur = 0; i < n; i++) {
    if (s[i] == '1') {
      range.push_back({cur, i});
      if (i + 1 < n && s[i + 1] == '1') {
        range.push_back({cur + 1, i + 1});
      }
      i++;
      cur += 2;
    }
  }
  long long ans = 0;
  for (int i = 0; i < (int) range.size(); i++) {
    if (range[i].first & 1) {
      if (range[i].second & 1) range[i].second--;
      int tim = (range[i].second - range[i].first + 1) / 2;
      tim = max(tim, 0);
      ans += tim;
    } else {
      int tim = n - range[i].first;
      tim -= (range[i].second - range[i].first + 1) / 2;
      ans += tim;
    }
  }
  cout << ans << '\n';
  return 0;
}