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

"""

なるべく各操作における奇数文字目に1をいれる
最後にたす数は確定

左端が1の時、最初に入れない理由はない
最初に必要な1を全部入れない理由、あるか？
なさそう

あとはどう0を入れていくか
1のうち、いくつが空数番目・いくつが奇数番目にいあるかを考える

0を入れると、それ以降の1の偶奇がひっくり返る
差は高々1
右端は毎回ひっくり返されるので考えなくていい
2番目は、右端で1回だけ延長できる
3番目は、2回延長できる

"""

T = input()

ans = 0
onum = 0

for i in T:

    if i == "1":
        onum += 1
        ans += (onum+1)//2

odd = []
eve = []

nodd = 0
neve = 0

#print (ans)

for i in range(len(T)-1,-1,-1):

    if T[i] == "0":
        odd.append(nodd)
        eve.append(neve)
        nodd = 0
        neve = 0
    else:
        if i % 2 == 0:
            nodd += 1
        else:
            neve += 1

#print (odd,eve)
ans += nodd * ( len(T) - onum )
#print (ans)

for i in range(len(odd)):

    now = 0
    if i == 0:
        now += len(odd)//2 * eve[i]
        now += (len(odd) - len(odd)//2) * odd[i]
    else:
        now += (len(odd)-i)//2 * eve[i]
        now += ((len(odd)-i) - (len(odd)-i)//2 ) * odd[i]
        rem = len(odd) - ( (len(odd)-i)//2 +(len(odd)-i) - (len(odd)-i)//2)
        
        now += rem * max(eve[i],odd[i])

    #print (now)
    ans += now

print (ans)
