CF2261E What Does the Cow Say?

Oh, Moo, Moo, Moo, I speak that normally! — Bessie the Cow Bessie gives you a regular bracket sequence (RBS) $ ^{\text{∗}} $ of length $ n $ and an integer $ k $ . In one operation, you can do the following: - Choose an index $ i $ ( $ 1 \le i \lt n $ ) such that $ s_i s_{i+1} = \mathtt{()} $ . - Let $ s' $ denote the string obtained after removing these two characters from $ s $ . - Set $ s := \mathtt{(} + s' + \mathtt{)} $ . You may perform this operation at most $ k $ times (possibly zero). It can be shown that $ s $ remains an RBS after every such operation. The score of an RBS is defined as the maximum number of consecutive opening brackets ' $ \texttt{(} $ ' in the string. For example, the score of the string " $ \texttt{(())((())())} $ " is $ 3 $ . Your task is to find the maximum possible score you can obtain by performing at most $ k $ operations on the given string. $ ^{\text{∗}} $ A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $ 1 $ and $ + $ between the original characters of the sequence. For example: - bracket sequences $ \texttt{()()} $ and $ \texttt{(())} $ are regular (the resulting expressions are: $ \texttt{(1)+(1)} $ and $ \texttt{((1+1)+1)} $ ); - bracket sequences $ \texttt{)(} $ , $ \texttt{(} $ and $ \texttt{)} $ are not.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2\le n \le 4 \cdot 10^5 $ , $ 0 \le k \le \frac{n}{2} $ ) — the length of the RBS and the maximum number of operations you may perform. The second line of each test case contains a string $ s $ of length $ n $ consisting of characters ' $ \texttt{(} $ ' and ' $ \texttt{)} $ ' — the given RBS. It is guaranteed that $ s $ is a regular bracket sequence, and that the sum of $ n $ over all test cases does not exceed $ 4 \cdot 10^5 $ .

For each test case, print a single integer — the maximum score you can obtain by performing at most $ k $ operations.

In the first test case, we cannot perform any operations. The maximum number of consecutive opening brackets is $ 1 $ . In the third test case, we can choose index $ i = 1 $ , performing the operation gives us $ s = $ " $ \texttt{(()())} $ ". Then, choosing index $ i = 4 $ gives us $ s = $ " $ \texttt{((()))} $ ". We used $ 2 $ operations and got a score of $ 3 $ , which is the maximum possible score. In the seventh test case, we can choose index $ i = 6 $ , performing the operation gives us $ s = $ " $ \texttt{(()(((((()))))))} $ ", which has a score of $ 6 $ . It can be shown that $ 6 $ is the maximum possible score achievable.