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 db;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define rrp(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc() ; !isdigit(tmp) ; tmp = gc())
    key = (tmp == '-');
  for ( ; isdigit(tmp) ; tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int N = 200010;
int n, val[N], num;
ll ans;
int main() {
  string str;
  cin >> str;
  n = (int)str.size();
  rep (i, 1, n) val[i] = str[i-1] - '0';
  rep (i, 1, n) num += val[i];
  rep (i, 1, num) ans += (i + 1) / 2;
  int rec = 0;
  rep (i, 1, n) {
    if (val[i] == 0) {
      ++ rec;
      continue;
    }
    int j = i;
    while (j + 1 <= n && val[j+1] == 1) ++ j;
    ans += (ll)((j - i + 1) / 2) * (n - num);
    if ((j - i + 1)&1) {
      int tmp = i / 2 - (i - rec) / 2;
      ans += n - num - tmp;
    }
    i = j;
  }
  cout << ans << endl;
  return 0;
}
