题目描述

题目译自 XXX Olimpiada Informatyczna – I etap Płytkie nawiasowania

由开括号和闭括号组成的字符串称为括号序列。括号序列是合法的，如果括号可以按照合法的嵌套方式成对匹配。我们还定义了嵌套深度。

形式上，合法的括号序列可以递归地定义为：

• 空字符串是合法的括号序列；它的嵌套深度为 $0$。
• 如果字符串 $w$ 是合法的括号序列，且其嵌套深度为 $h$，那么字符串 $\texttt{(}w\texttt{)}$，即在 $w$ 的开头和结尾分别添加一个开括号和闭括号，是合法的括号序列，且其嵌套深度为 $h+1$。
• 如果字符串 $w_{1}$ 和 $w_{2}$ 都是合法的括号序列，且其嵌套深度分别为 $h_{1}$ 和 $h_{2}$，那么字符串 $w_{1} w_{2}$，即将 $w_{1}$ 和 $w_{2}$ 拼接起来，是合法的括号序列，且其嵌套深度为 $\max (h_{1}, h_{2})$。

给定一个合法的括号序列 $w$ 和一个数 $H$。通过反转括号（将某个开括号变成闭括号或者将某个闭括号变成开括号），要使得括号序列的嵌套深度不超过 $H$，最少需要反转多少个括号？

输入格式

第一行包含两个整数 $n,H\ (2\leq n \leq 10^6,1 \leq H \leq \frac{n}{2})$，表示序列的长度和最大深度。

第二行包含一个由 $\texttt{(}$ 和 $\texttt{)}$ 组成的 $n$ 个字符的字符串，它是一个正确的括号表达式。

输出格式

输出一个整数，表示为了使得括号序列的嵌套深度不超过 $H$，所需的最少反转次数。

8 2
(()(()))

2

字符串 $\texttt{(()(()))}$ 的嵌套深度为 $3$。反转第五个和第六个括号，我们可以得到字符串 $\texttt{(()()())}$，其嵌套深度为 $2$。

仅反转一个括号是不够的，因为这样无法得到合法的括号序列。

样例 2

见附加文件下 [ply1.in](file:ply1.in) 和 [ply1.out](file:ply1.out)。

该样例满足 $n=20, w=\texttt{(((((((((())))))))))}, H=10$；答案是 $0$。

样例 3

见附加文件下 [ply2.in](file:ply2.in) 和 [ply2.out](file:ply2.out)。

该样例满足 $n=20, w=\texttt{(((((((((())))))))))}, H=1$；答案是 $10$。

样例 4

见附加文件下 [ply3.in](file:ply3.in) 和 [ply3.out](file:ply3.out)。

该样例满足 $n=10^6, w=\texttt{(}^{\frac{n}{2}}\texttt{)}^{\frac{n}{2}}, H=1$；答案是 $\frac{n}{2}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

令 $h$ 表示输入的括号表达式的深度。

子任务编号	额外限制	分值
$1$	$n \leq 20$	$20$
$2$	$n \leq 3000$	$40$
$3$	$H=h-1$	$20$
$4$	无额外限制	$20$