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
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string T;
  cin >> T;

  // Tから1文字ずつ削除していく

  // 1文字削除した以降は、偶数列と奇数列が入れ替わる

  // 「この削除を行ったとき、奇数列の1を、いくつ増やすことができるか？」
  // これを A とおく、その数を各削除位置に対して計算する

  // A = そこより後（その位置を含まない）の偶数の数 - そこ以降（その位置を含む）の奇数の数
  // Aが最大の部分を削除していけば良い（ただしAが最大で 1 と 0 があれば 0 を優先して消す）

  // ただし単純にAを計算するとO(N)かかり、N回削除だとO(N^2)で間に合わない

  //  o  e  o  e  o  e  o  e  o  e
  //  0  1  1  1  1  0  1  1  0  1 数列
  //     4     3     2     2     1 偶数列
  //   ／    ／    ／    ／    ／
  //  3     3     2     1     0    奇数列
  //  1  0  0  0  0  1  1  1  1  0 A

  //                 * ここを削除してみる

  //  o  e  o  e  o  e  o  e  o
  //  0  1  1  1  1  1  1  0  1 数列
  //     3     2     1     0    偶数列
  //   ／    ／    ／    ／    ／
  //  4     4     3     2     1 奇数列
  // -1 -2 -2 -2 -2 -2 -2 -1 -1 A

  // 削除位置以前は、範囲Add(Sub)
  // 削除位置以降は、位置が一つずれ減算順が逆になる

  // 
  // 解けないので解説を読む…
  //

  // > まず，1 を削除するのは 0 を全て削除してからでいいです。というのも 0 がまだ残っているなら，
  // 1 を削除する代わりにその 1 に最も近い 0 を削除することで，1 になっている箇所がより多い文字列
  // が得られるからです。

  // (a0個の 0) 1 (a1個の 0) 1 . . . 1 (ak個の 0)

  vector<int> zs;
  zs.push_back(0);

  // 偶数個の連続した1の数
  i64 eoc = 0;

  int prev = 0;
  int cnt = 0;
  T += '2';
  F0R(i, T.size()) {

    int n = T[i] - '0';

    if (n != prev) {
      if (prev == 1) {
        eoc += cnt & ~1;
        if (cnt & 1) {
          zs.push_back(0);
        }
        cnt = 0;
        prev = 0;
      }
      else if (prev == 0) {
        zs.back() += cnt;
        cnt = 0;
        prev = 1;
      }
    }
    cnt++;
  }

  //Print(zs);
  //debug(eoc);

  i64 result = 0;
  F0R(i, zs.size()) {

    // 削除すべき数
    int dc = i ? zs[i] - 1 : zs[i];

    if (dc <= 0) continue;

    // 0 を偶数個削除
    result += (i64)dc / 2 * (eoc + i * 2 + (zs.size() - i - 1));
    //debug(result);

    // 0 を1個削除
    if (dc & 1) {
      int n = 0;
      result += i + eoc / 2;
      F0R(j, zs.size() - 1) {
        n += zs[j] + 1;
        if (j < i) continue;
        if (n & 1) result++;
      }
    }
    //debug(result);
    
    zs[i] -= dc;
  }

  // 1個のこった0を右から順に削除
  //cout << "del <--0" << newl;
  RFO(i, 1, zs.size()) {
    if (zs[i]) {
      result += eoc / 2 + i;

      // ここより右の1の数
      int n = zs.size() - i - 1;
      result += (n + 1) / 2;
    }
  }

  // 残りは1だけなので順に削除
  int oc = eoc + zs.size() - 1;
  //debug(oc);
  //debug(result);
  // 1 2 3 4 5 6 ...
  // 1 1 2 2 3 3 ...

  if (oc & 1) result += (oc + 1) / 2;
  oc /= 2;
  result += ((i64)oc + 1) * oc;

  cout << result;
}
#endif
