由左括号和右括号组成的序列称为括号序列。如果括号可以配对且嵌套正确，则称该括号序列是合法的。我们同时定义嵌套深度。

形式化地，合法括号序列可以递归定义如下： 空序列是合法的括号序列，其深度为 0。 如果序列 $w$ 是深度为 $h$ 的合法括号序列，则序列 $(w)$（在开头添加左括号，在结尾添加右括号）是深度为 $h+1$ 的合法括号序列。 * 如果序列 $w_1$ 和 $w_2$ 分别是深度为 $h_1$ 和 $h_2$ 的合法括号序列，则序列 $w_1w_2$（将它们拼接）是深度为 $\max(h_1, h_2)$ 的合法括号序列。

给定一个合法的括号序列 $w$ 和一个整数 $H$。括号翻转是指将某个左括号变为右括号，或反之。请问最少需要进行多少次括号翻转，才能得到一个深度不超过 $H$ 的合法括号序列？

输入格式

第一行包含两个整数 $n$ 和 $H$ ($n \ge 2, 1 \le H \le \frac{n}{2}$)，分别表示序列长度和最大深度。

第二行包含一个长度为 $n$ 的字符串，由字符 ( 和 ) 组成，是一个合法的括号序列。

输出格式

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

样例

输入格式 1

8 2
(()(()))

输出格式 1

2

说明

序列 (()(())) 的深度为 3。翻转第 5 个和第 6 个括号可以得到序列 (()()())，其深度为 2。 仅翻转一个括号是不够的，因为这样无法得到合法的括号序列。

测试用例

• 1ocen: $n = 20, w = (((((((((()))))))))), H = 10$; 答案为 0。
• 2ocen: $n = 20, w = (((((((((()))))))))), H = 1$; 答案为 10。
• 3ocen: $n = 1\,000\,000, w = (\frac{n}{2}) \frac{n}{2}, H = 1$; 答案为 $\frac{n}{2}$。

评分

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试数据组成。 令 $h$ 为输入序列的深度。