問題文

バンズ文字列とは、以下によって定義される、文字 ( および ) からなる文字列のことです。

1. 空文字列はバンズ文字列である。
2. $A$ がバンズ文字列であるとき、( と $A$ と ) を順に連結した文字列はバンズ文字列である。
3. $A$, $B$ がバンズ文字列であるとき、$A$ と $B$ を連結した文字列はバンズ文字列である。
4. これら以外の文字列はバンズ文字列ではない。

上のようにしてバンズ文字列を生成するにあたって、 2. によって同時に追加された ( と ) をペアにして、これを対応バンズと呼ぶことにします。
バンズ文字列では、任意の文字がある対応バンズに属し、どの文字も複数の対応バンズに属さないことがわかります。

また、バーガー文字列とは、以下によって定義される、文字 ( , ) および | からなる文字列のことです。

• 文字 | をすべて取り除くと、バンズ文字列になる。
• 文字 | は$2$つ以上連続しない。

長さ $N$ のバンズ文字列 $S$ が与えられます。 あなたは $S$ に文字 | を $K$ 個挿入し、バーガー文字列を作ることにしました。
バーガー文字列に含まれるある対応バンズの美味しさとは、その2文字 ( と ) の間にある | の個数のことです。
バーガー文字列の美味しさとは、それに含まれるすべての対応バンズの美味しさの和のことです。

あなたが作ることのできるバーガー文字列の美味しさの最大値を求めてください。

制約

• $1 \\leq K < N \\leq 10^5$
• $K$, $N$ は整数である。
• $|S|=N$
• $S$ はバンズ文字列である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $S$

出力

作ることのできるバーガー文字列の美味しさの最大値を出力せよ。

入力例 1

6 1
(())()

出力例 1

2

((|))() を作るのが最適です。

入力例 2

8 2
((()))()

出力例 2

5

(((|)|))() を作るのが最適です。