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 int long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fr(i,j,k) for(i = j; i < (k); i++)
#define all(x) x.begin(), x.end()
#define el '\n'
#define remax(a,b) a = max(a, b)
#define remin(a,b) a = min(a, b)
#define sz(x) int32_t(x.size())

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
// --------------------------------------------------------------------

const pii dxy[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
const int mod = 1e9 + 7;
const int INF = 2e18;
const ld EPS = 1e-9;
const int NN = 1e5 + 2;


struct info {
	bool value;
	int count, start;
};

string to_string(string s) {
	return '"' + s + '"';
}
string to_string(const char* s) {
	return to_string((string) s);
}
string to_string(bool b) {
	return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

string to_string(info f) {
	return "(" + to_string(f.value) +
	       ", " + to_string(f.count) +
	       ", " + to_string(f.start) + ")";
}

template <typename A>
string to_string(A v) {
	bool first = true;  string res = "{";
	for (const auto &x : v) {
		if (!first) { res += ", "; }
		first = false; res += to_string(x);
	}
	res += "}";         return res;
}
void debug_out() {
	cerr << endl;
}
template <typename Head, typename ... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T ...);
}

//#define TRACE

#ifdef TRACE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
//============================================================================


void solve() {
	int i = 0, j = 0, k = 0, n = 0, m = 0, ans = 0;
	string T;
	cin >> T;
      n = sz(T);
	vector<info> v;
	T = '0' + T;
	// k = total number of 1s
	for(i = n; i > 0; ) {
		for(j = i; j > 0 and T[j] == T[i]; j--);
		if(T[i] - '0') {
			k += (i-j);
			if(i-j == 1 or (i-j)%2 == 0) {
				v.pb({1, i-j, i});
			} else {
				v.pb({1, i-j-1});
				v.pb({1, 1, i});
			}

		} else {
			v.pb({0, i - j});
		}
            i = j;
	}
	reverse(all(v));
	debug(v);
	for(auto& h: v) {
		if(h.value) {
			if(h.count % 2 == 0) continue;
			int t = (h.start & 1) + m;
			t >>= 1;
			ans += t;
		} else {
			m += h.count;
		}
	}
	int tot0 = m;
	debug(tot0, k);
	m = 0;
	for(i = sz(v) - 1; i >= 0; i--) {
		if(v[i].value) {
			if(v[i].count & 1) {
				ans += m;
			} else {
				int t = v[i].count/2 * tot0;
				ans += t;
			}
		} else {
			m += v[i].count;
		}
	}
      debug(ans);
	for(i = k; i > 0; i -= 2) ans += i;
	cout << ans << el;
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int T = 1;
	// cin >> T;
	for(int tc = 1; tc <= T; tc++) {
		solve();
	}
	return 0;
}