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 自动生成**