← 返回题目列表

Codeforces · 1488/B

B. RBS 删除

中文机器翻译题面 查看原题

括号序列是仅包含字符“(”和“)”的字符串。常规括号序列(或者简称为 RBS)是可以通过在序列的原始字符之间插入字符“1”和“+”来转换为正确的算术表达式的括号序列。例如:

- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。

给你一个字符串 $$$s$$$,它是一个 RBS。您可以对此字符串应用任意数量的操作。每个操作可以具有以下类型之一:

1.选择$$$s$$$的一些非空前缀并将其从$$$s$$$中删除,因此$$$s$$$仍然是RBS。例如,我们可以按如下方式应用此操作: "(())()(())()()" $$$\to$$$ "()()" (前 $$$10$$$ 字符被删除);
2.选择$$$s$$$的一些连续的非空子串并将其从$$$s$$$中删除,因此$$$s$$$仍然是RBS。例如,我们可以按如下方式应用此操作:“(())()(())()()” $$$\to$$$ “(())()()()”(从第 $$$7$$$ 到第 $$$10$$$ 的字符被删除)。

操作 $$$2$$$ 最多可以应用 $$$k$$$ 次。计算在 $$$s$$$ 变空之前可以应用的最大操作数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。

每个测试用例由两行描述。第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$; $$$n$$$ 是偶数) — $$$s$$$ 的长度以及您可以应用的 $$$2$$$ 类型的最大操作数。

第二行包含一个由 $$$n$$$ 个字符“(”和“)”组成的字符串 $$$s$$$。该字符串是 RBS。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您可以应用的最大操作数。

示例

输入 #1

3
12 2
(()())((()))
6 3
()()()
8 1
(((())))

输出 #1

4
3
2