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.InputStreamReader;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final String str = in.nextLine();
        final char[] s = (' ' + str).toCharArray();
        final int n = str.length();
        int cnt1 = 0;
        int cnt0 = 0;
        long res = 0;
        for (int i = 1; i <= n; ++i) {
            cnt1 += (s[i] == '1') ? 1 : 0;
            cnt0 += (s[i] == '0') ? 1 : 0;
        }
        for (int i = 1; i <= cnt1; ++i) {
            res += (i + 1) / 2;
        }
        for (int i = 1, now = 0, x = 0, y = 0; i <= n; ++i) {
            if (s[i] == '1') {
                ++now;
                ++y;
                if ((y & 1) == 1) {
                    res += x / 2;
                } else {
                    res += (x + 1) / 2;
                }
                if ((now & 1) == 1) {
                    res += cnt0 - x;
                }
            } else {
                ++x;
                if ((now & 1) == 1) {
                    ++now;
                }
            }
        }
        System.out.println(res);
    }
}
