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 <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int MAXN = 200228;



int sum[MAXN];
bool del[MAXN];
int cnt[2];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 //	read(FILENAME);
	string s;
	cin >> s;
	for (int i = sz(s) - 1; i >= 0; i--) {
		if (s[i] == '1') {
			sum[i]++;
		}
		sum[i] += sum[i + 2];
	}
	ll ans = sum[0];
	int last = 0;
	int cnts = 0;
	for (int i = 0; i < sz(s) - 1; i++) {
		if (s[i] == '1' && last == 0) {
			cnts++;
		}
		if (last == 0 && s[i] == '0' && s[i + 1] == '1') {
			del[i] = true;
			ans += cnts + sum[i + 1];
		} else {
			last = 1 - last;
		}
	}
	string t;
	for (int i = 0; i < sz(s); i++) {
		if (!del[i]) {
			t += s[i];
		}
	}
	s = t;
	vector<int> pr(sz(s));
	for (int i = 0; i < sz(s); i++) {
		pr[i] = (i % 2 == 0 ? s[i] - '0': 0);
		if (i > 0) {
			pr[i] += pr[i - 1];
		}
	}
	for (int i = sz(s) - 1; i >= 0; i--) { 
		cnt[i % 2] += s[i] - '0';
		if (s[i] == '0') {
			swap(cnt[0], cnt[1]);
			ans += cnt[0] + pr[i];
		}
	}
	int cnt1 = 0;
	for (int i = 0; i < sz(s); i++) {
		cnt1 += (s[i] == '1');
	}
	for (int i = 0; i < cnt1; i++) {
		ans += (cnt1 - i) / 2;
	}
	cout << ans << endl;
	return 0; 	
}
