H. Square Root
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little A has a string that only contains the characters 0 and 1 (hereafter referred to as a 01 string). He likes 1 and dislikes 0, so in Little A's eyes, there are only 1s in a 01 string.

Specifically, for a 01 string, Little A sees 0 as a separator that divides the string into several substrings consisting entirely of 1s. For example, for a 01 string 010011101111101, Little A sees four substrings that consist only of 1s: 1, 111, 11111, and 1.

For a 01 string, Little A defines its charm value as the sum of the square roots of the lengths of the separated substrings that consist entirely of 1s. For example, for the string 010011101111101, Little A's charm value is $$$\sqrt{1}+\sqrt{3}+\sqrt{5}+\sqrt{1}=2+\sqrt{3}+\sqrt{5}$$$.

Now, given a 01 string $$$s$$$, Little A hopes you can change some of the 1s in $$$s$$$ to 0s (or leave them unchanged) to maximize the charm value of this 01 string.

Input

A single line containing a string $$$s$$$ that consists only of the characters 0 and 1 ($$$1\leq |s|\leq 10^6$$$).

Output

A single line containing a floating-point number that represents the maximum charm value that can be obtained after the changes. Your answer is considered correct if the relative or absolute error compared to the standard answer does not exceed $$$10^{-9}$$$.

Assuming your answer is $$$a$$$ and the standard answer is $$$b$$$, it is considered correct if $$$\frac{|a-b|}{\max\{b,1\}}\leq 10^{-9}$$$.

Example
Input
1100110111
Output
4.8284271247
Note

Changing the 9th 1 to 0 will yield the maximum charm value of $$$2+2\sqrt{2}$$$.