AT_cpsco2019_s2_c Delicious Burgers

[problemUrl]: https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_c バンズ文字列とは、以下によって定義される、文字 `(` および `)` からなる文字列のことです。 1. 空文字列はバンズ文字列である。 2. $ A $ がバンズ文字列であるとき、`(` と $ A $ と `)` を順に連結した文字列はバンズ文字列である。 3. $ A $, $ B $ がバンズ文字列であるとき、$ A $ と $ B $ を連結した文字列はバンズ文字列である。 4. これら以外の文字列はバンズ文字列ではない。 上のようにしてバンズ文字列を生成するにあたって、 2. によって同時に追加された `(` と `)` をペアにして、これを対応バンズと呼ぶことにします。 バンズ文字列では、任意の文字がある対応バンズに属し、どの文字も複数の対応バンズに属さないことがわかります。 また、バーガー文字列とは、以下によって定義される、文字 `(` , `)` および `|` からなる文字列のことです。 - 文字 `|` をすべて取り除くと、バンズ文字列になる。 - 文字 `|` は$ 2 $つ以上連続しない。 長さ $ N $ のバンズ文字列 $ S $ が与えられます。 あなたは $ S $ に文字 `|` を $ K $ 個挿入し、バーガー文字列を作ることにしました。 バーガー文字列に含まれるある対応バンズの美味しさとは、その2文字 `(` と `)` の間にある `|` の個数のことです。 バーガー文字列の美味しさとは、それに含まれるすべての対応バンズの美味しさの和のことです。 あなたが作ることのできるバーガー文字列の美味しさの最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ S $

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

### 制約 - $ 1\ \leq\ K $ - $ K $, $ N $ は整数である。 - $ |S|=N $ - $ S $ はバンズ文字列である。 ### Sample Explanation 1 `((|))()` を作るのが最適です。 ### Sample Explanation 2 `(((|)|))()` を作るのが最適です。