A chat message contains lowercase letters and the parentheses ( and ). The letters are irrelevant; only the parentheses matter. Report the minimum number of parenthesis characters you must delete so that the parentheses left in the string are balanced (every ( has a later matching ) and vice versa). Deleting a character removes exactly that one parenthesis; letters are never deleted and never affect balance.
Input format
A single line: the message (it may be empty). It contains only lowercase letters and the characters ( and ).
Output format
A single integer: the minimum number of parentheses to delete.
Constraints
- 0 <= length of the message <= 1000
- The message contains only lowercase letters,
(, and).