Problem Description

A buns string is a string consisting of the characters ( and ), defined as follows:

1. The empty string is a buns string.
2. If $ A $ is a buns string, then the string obtained by concatenating (, $ A $, and ) in this order is a buns string.
3. If $ A $ and $ B $ are buns strings, then the string obtained by concatenating $ A $ and $ B $ is a buns string.
4. No other strings are buns strings.

In generating a buns string as described above, we call a pair of ( and ) added simultaneously by rule 2 a corresponding buns. In a buns string, every character belongs to some corresponding buns, and no character belongs to multiple corresponding buns.

A burger string is a string consisting of the characters (, ), and |, defined as follows:

• Removing all | characters results in a buns string.
• | characters do not appear consecutively more than once.

You are given a buns string $ S $ of length $ N $. You decide to insert $ K $ | characters into $ S $ to create a burger string. The deliciousness of a certain corresponding buns in a burger string is the number of | characters between the two characters ( and ). The deliciousness of a burger string is the sum of the deliciousness of all its corresponding buns.

Find the maximum deliciousness of the burger string you can create.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ S $

Output Format

Output the maximum deliciousness of the burger string you can create.

Sample Input and Output

Sample Input #1

6 1
(())()

Sample Output #1

2

Sample Input #2

8 2
((()))()

Sample Output #2

5

Notes/Hints

Constraints

• $1 \leq K$
• $ K $ and $ N $ are integers.
• $ |S| = N $
• $ S $ is a buns string.

Sample Explanation 1

Creating ((|))() is optimal.

Sample Explanation 2

Creating (((|)|))() is optimal.

见题面 Input 部分

见题面 Output 部分