Minimum cost of a correct parenthesization (1) P76915

Given a word made up of only opening and closing parentheses, we must make it a correct parenthesization. The only allowed operation is turning each parenthesis, that is, changing its orientation. What is the minimum number of turns needed?

For example, if the word is “)(()((()”, then we can achieve the correct parenthesization “((())())” just turning three parentheses, and we cannot do better.

Input

Input consists of several cases, each with a word with n opening or closing parentheses. You can assume that n is even and between 2 and 100.

Output

For every case, print the minimum cost of a correct parenthesization.

Hint

Although there are more efficient solutions, a dynamic programming with time cost Θ(n³ ) and space cost Θ(n² ) should be enough.