← 返回题目列表

AtCoder · cpsco2019_s2_c

C. 美味的汉堡

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

配点 : 300 点

問題文

小圆面包字符串是由以下定义的字符串: 由 ( 和 给出了 ) 组成的字符串。

  1. 空串是包子串。 当
  2. A 是包子串时, 由( 和 A 和 ) 按顺序连接而成的字符串是包子字符串。 与
  3. A, B 是包子串时, 由A 和 B 连接的字符串是一个包子字符串。
  4. 这些以外的字符串不是包子字符串。

如上生成包子字符串时,同时添加了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

(((|)|))() 。