A sequence consisting of opening and closing parentheses is called a parenthesis sequence. A parenthesis sequence is correct if the parentheses can be paired such that they are correctly nested. We also define the nesting depth.

Formally, a correct parenthesis sequence can be defined recursively: The empty sequence is a correct parenthesis sequence; its depth is 0. If $w$ is a correct parenthesis sequence of depth $h$, then the sequence $(w)$, formed by adding an opening parenthesis at the beginning and a closing parenthesis at the end, is a correct parenthesis sequence of depth $h + 1$. * If $w_1$ and $w_2$ are correct parenthesis sequences of depths $h_1$ and $h_2$ respectively, then the sequence $w_1w_2$, formed by concatenating them, is a correct parenthesis sequence of depth $\max(h_1, h_2)$.

You are given a correct parenthesis sequence $w$ and a number $H$. By a parenthesis flip, we mean changing an opening parenthesis to a closing one or vice versa. What is the minimum number of parenthesis flips required to obtain a correct parenthesis sequence with a depth no greater than $H$?

Input

The first line of input contains two integers $n$ and $H$ ($n \ge 2$, $1 \le H \le \frac{n}{2}$), representing the length of the sequence and the maximum depth.

The second line contains an $n$-character string consisting of the characters ( and ), which is a correct parenthesis sequence.

Output

Your program should output a single integer representing the minimum number of parenthesis flips required to obtain a correct parenthesis sequence with a depth of at most $H$.

Examples

Input 1

8 2
(()(()))

Output 1

2

Note

The sequence (()(())) has a depth of 3. Flipping the fifth and sixth parentheses gives the sequence (()()()) with a depth of 2. A single flip is not enough, as it would not result in a correct parenthesis sequence.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups. Let $h$ denote the depth of the parenthesis sequence given in the input.