You have surely heard of bracket expressions before, but just in case, let us refresh our memory with their definition: The word () is a valid bracket expression. If $S$ is a valid bracket expression, then the word $(S)$ is also a valid bracket expression. If $S_1$ and $S_2$ are valid bracket expressions, then the word $S_1S_2$ is also a valid bracket expression. No word not generated by the above rules is a valid bracket expression.

The "bracketness" of a word consisting only of the characters '(' and ')' is defined as the number of its substrings that are valid bracket expressions. Each substring is counted as many times as it occurs in the given word.

You are given a word of length $n$ consisting only of the characters '(' and ')', and a number $k$. This word does not necessarily have to be a valid bracket expression. Your task is to divide it into $k$ non-empty intervals (each character must belong to exactly one interval) such that the sum of the bracketness of the resulting words is minimized.

Input

The first line of standard input contains two integers $n$ and $k$ ($1 \le k \le n \le 100\,000$), representing the length of the word and the number of intervals into which we want to divide it, respectively. The second line contains a word of length $n$ consisting only of the characters '(' and ')'.

Output

The only line of output should contain a single integer, representing the minimum possible sum of the bracketness of the $k$ words obtained by an optimal division of the input word.

Examples

Input 1

15 2
())(()())()(())

Output 1

6

Input 2

15 3
())(()())()(())

Output 2

3

Note

Explanation of the examples: In the first example test, an optimal division of the word is, for example: ())(()())()(()) = ())(( | ))()(())

The first word contains two valid bracket expressions: () ()

The second word contains four valid bracket expressions: () () () ()

The sum of the bracketness of the words is therefore 6.

In the second example test, an optimal division of the word is, for example: ())(()())()(()) = ())(( | )())()(( | ))

Subtasks

• In some test groups, $n \le 18$.
• In some test groups, $n \le 300$.
• In some test groups, $n \le 4000$.
• In some test groups, $k \le 30$.

For each of the cases mentioned above, there exists at least one group that satisfies it. These groups may or may not be disjoint for different conditions.