AT_dwango2017final_a 計算ドリル

[problemUrl]: https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a ニコニコテレビちゃんは、頭の体操として簡単な計算をすることにしました。 ところでニコニコテレビちゃんは人間ではないので、逆ポーランド記法で計算をします。 具体的には、`0` ~ `9`, `-`, `+` からなる文字列 $ S $ について、以下の規則に従い計算をします。 - まず、最初の時点では空の、無限に長いスタックを $ 1 $ つ持っていると考える。そして、$ S $ の文字を前から見ていく。 - もし`0` ~ `9`が出てきたら、そのままスタックへ積む。 - もし`+`が出てきたら、スタックから1個取り出し $ a $、もう1個取り出し $ b $ とする。そして $ b+a $ をスタックへ積む。 - もし`-`が出てきたら、スタックから1個取り出し $ a $、もう1個取り出し $ b $ とする。そして $ b-a $ をスタックへ積む。 - 最後に、スタックの中身が $ 1 $ 個ならばそれが答えである - もし $ 1 $ 個ではなかったり、途中で取り出そうとしたがスタックが空だったりした場合は $ S $ は正しい式ではない。 ニコニコテレビちゃんは、適当に文字列 $ S $ を書きました。 これに対してただ計算するだけではつまらないので、以下の問題を解くことにしました。 - この文字列を $ K $ 文字まで書き換えて、正しい式にできるか？また、出来るならば正しい式のうち、計算した答えの最大値はいくつか？ しかしこれは難しすぎたので、あなたが代わりに解いて助けてあげてください。

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

もし正しい式に出来ないならば `NG` と出力してください。 出来るならば `OK` と出力し、更に次の行に計算した答えの最大値を出力してください。

### 制約 - $ S $ は、`0` ~ `9`、`-`、`+` からなる文字列である - $ 1\ ≦\ |S|\ ≦\ 52 $ - $ 0\ ≦\ K\ ≦\ |S| $ ### Sample Explanation 1 この式は、普通の記法で表すと`2+1`となります ### Sample Explanation 2 `29+`に書き換えると、答えが最大になります ### Sample Explanation 3 `91-`に書き換えると、答えが最大になります ### Sample Explanation 4 このような式は、逆ポーランド記法としては正しい式ではありません ### Sample Explanation 5 `12+4+6+`と書き換えると、答えが最大になります