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 sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

t = input()
s = t.replace("0", "")
q = len(s) # 1の数
n = len(t)
ps = [None]*(q+1)
c = 0
j = 0
for tmp in t:
    if tmp=="1":
        ps[j] = c
        j += 1
        c = 0
    else:
        c += 1
ps[-1] = c

dp = [0] * q # インデックスqの1までのベストな配置のときの奇数の個数
pp = [0] * (q+1) # 上を実現するために使うpsの個数
if not dp:
    print(0)
else:
    dp[0] = 1
    j = 1 # j : トータルのインデックス(1はじまり)
    for i in range(1,q):
        j += 1
        p = ps[i]
        if j%2:
            pp[i] = 0
            dp[i] = dp[i-1] + 1
        elif p:
            pp[i] = 1
            j += 1
            dp[i] = dp[i-1] + 1
        else:
            pp[i] = 0
            dp[i] = dp[i-1]
    if q%2==0:
        ans = q//2 * (q//2 + 1)
    else:
        ans = q//2 * (q//2 + 1) + q//2 + 1
    
    # 1をすべて入れたあとに得られる利得
    # ppを前から順にいれていく
    j = 0
    for i in range(q+1):
        j += 1
        if not pp[i]:
            continue
        # 0を１個いれる
        j += 1
        ans += dp[i]
        if j%2:
            ans += (q-i-1) // 2
        else:
            ans += (q-i-1) // 2 + (q-i-1)%2
    
    # 残りのpsを後ろから順にいれていく
    o = 0 # 現時点より後ろの(jを0としたときの)奇数番目の1の個数
    e = 0 # 現時点より後ろの(jを0としたときの)偶数番目の1の個数
    j = q + sum(pp) # 現在地のインデックス(1はじまり)
    for i in range(q, 0, -1):
        num = ps[i] - pp[i]
        if num>0:
            ans += dp[i-1] * num
            if num%2==0:
                ans += (num//2)*o + (num//2)*e
            else:
                ans += (num//2)*o + (num//2)*e + (e if j%2==0 else o)
                e,o = o,e
        j -= 1
        if pp[i-1]:
            j -= pp[i-1]
            e += 1
        else:
            o, e = 1 + e, o

    # 最初の0を入れる
    num = ps[0] - pp[0]

    if num%2==0:
        ans += (num//2)*o + (num//2)*e
    else:
        ans += (num//2)*o + (num//2)*e + e if j%2==0 else o

    print(ans)