eolymp
bolt
Try our new interface for solving problems
Problems

Brackets

Brackets

Let S be a proper bracketing sequence if it consists only of characters '{', '}', '[', ']', '(', ')' and takes place at least one of the following three conditions:

  1. S is an empty string;
  2. S can be represented in the form S = S1 + S2 + S3 + ... + Sn (n > 1), where Si are nonempty proper bracketing sequences, and sign "+" means the concatenation of the strings;
  3. S can be represented in the form S = { + C + } or S = [ + C + ] or S = ( + C + ), where C is a proper bracketing sequence.

One string is given, consisting of symbols '{', '}', '[', ']', '(', ')'. Find the minimum number of characters to be inserted in it in order to make the correct bracket sequence.

Input

One string consisting of no more than 100 symbols '{','}', '[',']', '(',')'.

Output

Print one non-negative integer - the answer to the problem.

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

Output example #2
0