题目描述

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

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

1. 空字符串是合法的括号序列；它的嵌套深度为 0。
2. 如果字符串 ( w ) 是合法的括号序列，且其嵌套深度为 ( h )，那么字符串 (w)（即在 ( w ) 的开头和结尾分别添加一个开括号和闭括号）是合法的括号序列，且其嵌套深度为 ( h+1 )。
3. 如果字符串 ( w_1 ) 和 ( w_2 ) 都是合法的括号序列，且其嵌套深度分别为 ( h_1 ) 和 ( h_2 )，那么字符串 ( w_1w_2 )（即将 ( w_1 ) 和 ( w_2 ) 拼接起来）是合法的括号序列.

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

输入格式

第一行包含两个整数 ( n, H )，表示序列的长度和最大深度。

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

输出格式

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

样例 1

输入

8 2
(()(()))

输出

2

说明

字符串 (()(())) 的嵌套深度为 3。反转第五个和第六个括号，我们可以得到字符串 (()()())，其嵌套深度为 2。仅反转一个括号是不够的，因为这样无法得到合法的括号序列。