AT_dwango2017final_a 計算ドリル

[problemUrl]: https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a ニコニコテレビちゃん为了锻炼大脑，决定做一些简单的计算。不过，由于ニコニコテレビちゃん不是人类，所以它使用逆波兰表示法进行计算。 具体来说，对于由 `0` ~ `9`、`-`、`+` 组成的字符串 $S$，按照以下规则进行计算： - 首先，假设有一个空的、无限长的栈。然后，从头开始依次读取 $S$ 的每个字符。 - 如果遇到 `0` ~ `9`，则直接压入栈中。 - 如果遇到 `+`，则从栈中取出一个数 $a$，再取出一个数 $b$，然后将 $b+a$ 压回栈中。 - 如果遇到 `-`，则从栈中取出一个数 $a$，再取出一个数 $b$，然后将 $b-a$ 压回栈中。 - 最后，如果栈中只剩下一个数，则该数即为答案。 - 如果栈中不只一个数，或者在取数时栈已空，则说明 $S$ 不是一个合法的表达式。 ニコニコテレビちゃん随意写下了一个字符串 $S$。它觉得仅仅计算结果太无聊了，于是提出了如下问题： - 最多可以修改 $K$ 个字符，将该字符串变为一个合法的表达式吗？如果可以，在所有合法表达式中，计算结果的最大值是多少？ 不过这个问题太难了，所以请你帮它解决。

输入通过标准输入给出，格式如下： > $K$ $S$

如果无法通过最多 $K$ 次修改将其变为合法表达式，则输出 `NG`。如果可以，则输出 `OK`，并在下一行输出计算结果的最大值。

### 限制条件 - $S$ 由 `0` ~ `9`、`-`、`+` 组成 - $1 \leq |S| \leq 52$ - $0 \leq K \leq |S|$ ### 样例解释 1 该表达式用普通记法表示为 `2+1`。 ### 样例解释 2 可以将其改写为 `29+`，此时答案最大。 ### 样例解释 3 可以将其改写为 `91-`，此时答案最大。 ### 样例解释 4 这种表达式作为逆波兰表示法不是合法表达式。 ### 样例解释 5 可以将其改写为 `12+4+6+`，此时答案最大。 由 ChatGPT 4.1 翻译