Problem Brief

Maximize Segregation Cost

An engineer is working to build an integrated binary circuit that takes input a binary string. A binary string consisting of only 0s and 1s can be segregated by moving all the 1s towards the end of the string. For example, the string "01010", after segregation becomes "00011".

In a single operation, any "1" from the binary string can be chosen and moved to the right until it reaches the end of the string or another "1". The cost of the operation is 1 + the number of places the one is moved. For example, in the string "100010", the first one can be moved three places to the right in cost 4. Note that it is mandatory to move a 1 to the maximum possible position to the right.

Given a binary string s, find the maximum number of operations possible to segregate the given string.

Function Description

Complete the function maximizeSegregationCost in the editor.

maximizeSegregationCost has the following parameter:

String s: a binary string

Returns

int: the maximum number of operations possible to segregate the given string

1Example 1

Input

s = "110100"

Output

Explanation

The final string should be "000111". The optimal way to maximize the number of operations will be:

Swap the second and the third characters at a cost of 2. The string becomes "101100".

Swap the first and the second characters at a cost of 2. The string becomes "011100".

Now, we move each one to the end i.e. moving 2 places at a cost of 3 each.

The total cost of segregation is 2 + 2 + 3 * 3 = 13. Hence the answer is 13.