AT_cpsco2019_s2_c.Delicious Burgers

「汉堡字符串」由字符 ( 和 ) 组成，定义如下：

1. 空字符串是一个汉堡字符串。
2. 若 $A$ 是汉堡字符串，则 ( + $A$ + ) 也是汉堡字符串。
3. 若 $A$ 和 $B$ 都是汉堡字符串，则 $A$ + $B$ 也是汉堡字符串。
4. 其他任何字符串都不是汉堡字符串。

在形成汉堡字符串的过程中，通过第 2 条规则添加的 ( 和 ) 是一对匹配的汉堡。在汉堡字符串中，每个字符仅属于一对匹配的汉堡。

另外，「汉堡串字符串」由字符 (、) 和 | 组成，需满足以下条件：

• 去掉 | 后，余下的部分为一个汉堡字符串。
• | 不能连续出现两个或更多。

现在给定一个长度为 $N$ 的汉堡字符串 $S$。你可以在 $S$ 中插入 $K$ 个 |，形成一个汉堡串字符串。
对每对匹配的汉堡来说，汉堡串字符串的美味度就是它的 ( 和 ) 之间 | 的数量。
整体汉堡串字符串的美味度是其所有匹配的汉堡的美味度总和。

请找出所能构造的汉堡串字符串的最大美味度。

标准输入包含：

$N$ $K$ $S$

输出最大可能的汉堡串字符串的美味度。

• $1 \leq K$
• $K$ 和 $N$ 为整数。
• $|S| = N$
• $S$ 是一个汉堡字符串。

样例说明

1. 通过插入 ((|))() 获得最大美味度。
2. 通过插入 (((|)|))() 获得最大美味度。

本翻译由 AI 自动生成