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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	
	static int tot;
	static boolean[] par;
	static int[] nextPar;
	static long[] minus;
	
	static void calc(int pos, boolean inv) {
		if (pos == tot) {
			return;
		}
		if (par[pos] != inv) {
			calc(pos + 1, !inv);
			minus[pos] = minus[pos + 1];
			nextPar[pos] = nextPar[pos + 1] + 1;
		} else {
			calc(pos + 1, inv);
			minus[pos] = minus[pos + 1] + nextPar[pos + 1] + 1;
			nextPar[pos] = tot - pos - 1 - nextPar[pos + 1];
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		char[] vals = sc.next().toCharArray();
		tot = 0;
		par = new boolean[vals.length];
		int ones = 0;
		long ans = 0;
		for (int i = 0; i < vals.length; i++) {
			ans += i / 2 + 1;
			if (vals[i] == '0') {
				par[tot++] = ones % 2 == 1;
			} else {
				ones++;
			}
		}
		
		nextPar = new int[tot + 1];
		minus = new long[tot + 1];
		
		calc(0, false);
		out.println(ans - minus[0]);
		
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}
