괄호 끼워넣기

승현이는 올바른 괄호열 (()(()))()()를 가지고 놀다가 이 괄호열을 여러 조각으로 부러뜨렸습니다. 조각을 살펴보니 다시 쓸 수 있는 것은 )))() 하나뿐이었고, 이 조각은 올바른 괄호열이 아닙니다.

지학이는 앞과 뒤에 괄호를 적당히 붙이면 올바른 괄호열이 된다고 알려 주었습니다. 실제로 )))()의 앞에 여는 괄호 3개를 붙이면 ((()))()가 되어 올바른 괄호열이 됩니다.

괄호를 사서 붙이는 데에는 돈이 들고 많이 붙일수록 놀기가 불편하므로, 승현이는 되도록 적게 붙이려고 합니다.

올바르지 않은 괄호열 S가 주어질 때, S의 앞과 뒤에만 괄호를 붙여 올바른 괄호열로 만드는 데 필요한 괄호의 최소 개수를 구하는 프로그램을 작성하세요. 괄호를 S의 중간에 끼워 넣을 수는 없습니다.

첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S는 여는 괄호 (와 닫는 괄호 )로만 이루어지며, 길이는 1 이상 50 이하입니다.

첫 번째 줄에 S를 올바른 괄호열로 만들기 위해 앞과 뒤에 붙여야 하는 괄호의 최소 개수를 출력합니다. 불가능한 경우는 입력으로 주어지지 않습니다.

괄호열은 여는 괄호 (와 닫는 괄호 )로만 이루어진 문자열입니다.

올바른 괄호열은 다음과 같이 정의합니다.