配点 : 300 点
問題文
小圆面包字符串是由以下定义的字符串:
由 ( 和
给出了 ) 组成的字符串。
- 空串是包子串。 当
- A 是包子串时,
由
(和 A 和)按顺序连接而成的字符串是包子字符串。 与 - A, B 是包子串时, 由A 和 B 连接的字符串是一个包子字符串。
- 这些以外的字符串不是包子字符串。
如上生成包子字符串时,同时添加了2.。
让我们将 ( 和 ) 配对并称它们为匹配面包。
在包子字符串中,我们知道任何字符都属于某个匹配的包子,并且没有字符属于多个匹配的包子。
汉堡字符串是由以下定义的字符串:
如果删除所有 ( , ) 和
给出了 | 组成的字符串。
- 文字
|,你会得到一个面包串。 - 文字
|为2连续不超过两次。
长度
包子串 N 给出了 S 。你是 S 中的字符
我决定插入 | 的 K 并创建一个汉堡字符串。
汉堡字符串中包含的某个匹配面包的美味程度由这两个字母决定。
之间 ( 和 ) 这是 | 的号码。
汉堡串的美味度是其包含的所有匹配面包的美味度之和。
找出你能制作的汉堡串的最大美味。
制約
- 1 \leq K < N \leq 10^5
- K, N 是一个整数。
- |S|=N
- S 是一个包子串。
入力
输入将以以下格式从标准输入给出。
N K S
出力
输出可以创建的汉堡串的最大美味度。 最好制作
入力例 1
6 1 (())()
出力例 1
2
((|))() 。
入力例 2
8 2 ((()))()
出力例 2
5
(((|)|))() 。