Let S be a proper bracketing sequence if it consists only of characters '{', '}', '[', ']', '(', ')' and takes place at least one of the following three conditions:
S is an empty string;
S can be represented in the form S = S[1]
+ S[2]
+ S[3]
+ ... + S[n]
(n > 1), where S[i]
are nonempty proper bracketing sequences, and sign "+" means the concatenation of the strings;
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.
One string consisting of no more than 100 symbols '{','}', '[',']', '(',')'.
Print one non-negative integer - the answer to the problem.