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;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string t;
  cin >> t;
  int32 n = t.size();
  
  //取り敢えず1を全部取る
  int32 cnt = 0;
  REP(i,n)if(t[i] == '1')++cnt;
  int64 ans = (1 + cnt/2) * (cnt/2);
  if(cnt % 2)ans += (cnt+1)/2;
  // ANS(ans);

  //前から順に偶数番目になるなら0埋めてく
  int32 cntuse = 0;
  REP(i,n){
    if(t[i] =='1'){
      ++cntuse;
      continue;
    }
    if(cntuse % 2 == 0)continue;
    t[i] = 2; //取った
    ++cntuse;
    ++cnt;
    ans += (cnt+1)/2;
  }
  // ANS(ans);

  //後ろから順に残りの0取ってく
  int32 cntodd1=0,cnteven1=0;
  FORR(i,n-1,0){
    if(t[i] =='1'){
      if(cntuse % 2 == 1){
        ++cntodd1;
      }else{
        ++cnteven1;
      }
    }
    if(t[i] != '0')--cntuse,--cnt;
    if(t[i] == '0'){
      swap(cntodd1,cnteven1);
      // cout << cntodd1 << " " << cnteven1 << " " << (cnt + 1) / 2 + cntodd1 << endl;
      ans += (cnt + 1) / 2 + cntodd1;
    }
  }
  ANS(ans);
}