Padding a bracket string

Seunghyun was playing with the correct bracket string (()(()))()() and snapped it into several pieces. Going through the pieces, he found that only )))() can be used again, and that piece is not a correct bracket string.

Jihak told him that attaching suitable brackets at the front and at the back turns it into a correct bracket string. Attaching three opening brackets in front of )))() gives ((()))(), which is correct.

Buying brackets costs money, and the more he attaches the harder the string is to play with, so Seunghyun wants to attach as few as possible.

Given an incorrect bracket string S, write a program that finds the minimum number of brackets to attach to the front and the back of S so that the result is a correct bracket string. Brackets cannot be inserted in the middle of S.

The first line contains the incorrect bracket string S. S consists only of opening brackets ( and closing brackets ), and its length is between 1 and 50.

Print on the first line the minimum number of brackets that must be attached to the front and the back of S to make it a correct bracket string. No impossible case is given as input.

A bracket string is a string made only of opening brackets ( and closing brackets ).

A correct bracket string is defined as follows.

• () is a correct bracket string.
• If A is a correct bracket string, then (A) is also a correct bracket string.
• If A and B are both correct bracket strings, then AB is also a correct bracket string.