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
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    t = input()[:-1]
    n = len(t)
    count_back_1 = [0]*n
    num_of_1 = 0
    cnt = 0
    for i in range(n-1, -1, -2):
        count_back_1[i] = cnt
        if t[i] == '1':
            cnt += 1
    num_of_1 += cnt
    cnt = 0
    for i in range(n-2, -1, -2):
        count_back_1[i] = cnt
        if t[i] == '1':
            cnt += 1
    num_of_1 += cnt
    # print(num_of_1)
    # print(count_back_1)

    ans = 0

    after_first_turn = [-1]*n
    after_first_turn_index = 0

    index = 0
    count_front_1 = 0
    while index < n:
        if t[index] == '1':
            after_first_turn[after_first_turn_index] = '1'
            if index == n-1:
                after_first_turn_index += 1
                break
            after_first_turn[after_first_turn_index+1] = t[index+1]
            index += 2
            count_front_1 += 1
            after_first_turn_index += 2
        else:
            ans += count_front_1
            ans += count_back_1[index]
            index += 1

        
    len_after_first_turn = after_first_turn_index    #  - 1
    # print(after_first_turn[:len_after_first_turn])
    # print(after_first_turn)
    if len_after_first_turn % 2 == 1:
        ans += (len_after_first_turn//2+1)
        len_after_first_turn -= 1
    half = len_after_first_turn//2
    ans += half*(half+1)
    print(ans)
    
    
