Minimum cost of a correct parenthesization (2) P10387

Given a word made up of only opening and closing parentheses and square brackets, we can do two kind of operations:

• Turning the orientation of a parenthesis or a square bracket. That is, we can convert ‘(’ into ‘)’, ‘)’ into ‘(’, ‘[’ into ‘]’, or ‘]’ into ‘[’. The cost is 1.
• Transforming a parenthesis into a square bracket or the other way around, but not changing its orientation. That is, we can convert ‘(’ into ‘[’, ‘)’ into ‘]’, ‘[’ into ‘(’, or ‘]’ into ‘)’. The cost is 2.

What is the minimum cost of converting a given word into a correct parenthesization? For instance, if the word is “](”, then we can get the correct parenthesization “[]” by two turns and one transformation, with total cost 4.

Input

Input consists of several cases. Every case consists of one word with opening and closing parentheses and square brackets. All the words have even sizes between 2 and 100.

Output

For every case, print the minimum cost of parenthesizing correctly.

Hint

The expected solution has time cost Θ(n³ ) and space cost Θ(n² ).