e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic programming

Correcting Parenthesization

Given a string of parentheses, we must turn it into a well formed string by changing as few characters as possible (we cannot delete or insert characters).

There are three kinds of parentheses: regular (), brackets [] and curly brackets {}. Each pair has an opening ('(', '[' and '{' respectively) and a closing (')', ']' and '}') character.

A well formed string of parentheses is defined by the following rules:

  • The empty string is well formed.
  • If s is a well formed string, (s), [s] and {s} are well formed strings.
  • If s and t are well formed strings, the concatenation st is a well formed string.

As examples, "([{}])", "" and "(){}[]" are well formed strings and "([}]", "([)]" and "{" are malformed strings.

For the given string of parentheses find the minimum number of characters that need to be changed to make it into a well formed string.

Input

Each line contains the string with even number of symbols '(', ')', '[', ']', '{', '}'. The length of each line is no more than 50.

Output

For each input string print in a separate line the minimum number of characters that need to be changed to make it into a well formed string.

Time limit 1 second
Memory limit 128 MiB
Input example #1
]()[((()
([)]
([{}[]
Output example #1
3
2
1