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
t=input()
n=len(t)
pos=[]
sum=0
for i in range(n):
  if t[i]=="1":
    sum+=1
  else:
    pos.append(sum)
x=(sum+1)//2*((sum+2)//2)
sz=len(pos)
cnt=0
res=[]
for i in range(sz):
  if ((pos[i]&1)^(cnt&1)):
    sum+=1
    cnt+=1
    x+=(sum+1)//2
  else:
    res.append(i)
res=res[::-1]
odd=0
even=0
for i in range(len(res)):
  sum+=1
  if i&1:
    odd = sz - res[i] - even
    x+=(sum+1)//2-odd
  else:
    even=sz-res[i]-odd
    x+=(sum+1)//2-even
print(x)