Minimum Bracket Flips to Limit Depth

You are given a valid parentheses string s and an integer H. The depth of a valid parentheses string is defined as follows:

• The empty string has depth \(0\).
• If \(w\) is a valid parentheses string with depth \(h\), then \((w)\) is a valid parentheses string with depth \(h+1\).
• If \(w_1\) and \(w_2\) are valid parentheses strings with depths \(h_1\) and \(h_2\) respectively, then their concatenation \(w_1w_2\) is a valid parentheses string with depth \(\max(h_1, h_2)\).

You can flip a character in the string as follows:

• If the current character is (, you may change it to ).
• If the current character is ), you may change it to (.

Your task is to flip some of the characters in s (potentially none) so that the resulting string is still a valid parentheses string and its depth does not exceed H. Find the minimum number of flips required.

inputFormat

The input consists of two lines:

1. The first line contains the valid parentheses string s.
2. The second line contains a single integer H representing the maximum allowed depth.

outputFormat

Output a single integer which is the minimum number of flips required so that the resulting valid parentheses string has a depth not exceeding H.

sample

()
1

0