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 math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0

odT = 0
tmpOd = True

for i in range(len(spT)):
    
    od = len(re.sub(r'0', '', spT[i][0 if tmpOd else 1::2]))
    ev = len(re.sub(r'0', '', spT[i][1 if tmpOd else 0::2]))
    odT += od
    vT.append(od - ev)
    if len(spT[i]) %2 == 1:
        tmpOd = not tmpOd

for i in reversed(range(1, len(spT))):
    odT = odT - vT[i]
    x += odT
    vT[i-1] -= vT[i]


print(x)