問題文

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

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 はバンズ文字列である。

入力例 1

6 1
(())()

出力例 1

2

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

入力例 2

8 2
((()))()

出力例 2

5

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