第3回 ドワンゴからの挑戦状 本選(オープンコンテスト)

A - 計算ドリル


Time limit時間制限 : 2.525sec / Memory limitメモリ制限 : 252.525MB

配点 : 500

問題文

ニコニコテレビちゃんは、頭の体操として簡単な計算をすることにしました。 ところでニコニコテレビちゃんは人間ではないので、逆ポーランド記法で計算をします。

具体的には、0 ~ 9, -, + からなる文字列 S について、以下の規則に従い計算をします。

  • まず、最初の時点では空の、無限に長いスタックを 1 つ持っていると考える。そして、S の文字を前から見ていく。
  • もし0 ~ 9が出てきたら、そのままスタックへ積む。
  • もし+が出てきたら、スタックから1個取り出し a、もう1個取り出し b とする。そして b+a をスタックへ積む。
  • もし-が出てきたら、スタックから1個取り出し a、もう1個取り出し b とする。そして b-a をスタックへ積む。
  • 最後に、スタックの中身が 1 個ならばそれが答えである
  • もし 1 個ではなかったり、途中で取り出そうとしたがスタックが空だったりした場合は S は正しい式ではない。

ニコニコテレビちゃんは、適当に文字列 S を書きました。 これに対してただ計算するだけではつまらないので、以下の問題を解くことにしました。

  • この文字列を K 文字まで書き換えて、正しい式にできるか?また、出来るならば正しい式のうち、計算した答えの最大値はいくつか?

しかしこれは難しすぎたので、あなたが代わりに解いて助けてあげてください。

制約

  • S は、0 ~ 9-+ からなる文字列である
  • 1 ≦ |S| ≦ 52
  • 0 ≦ K ≦ |S|

入力

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

K
S

出力

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


入力例 1

0
21+

出力例 1

OK
3

この式は、普通の記法で表すと2+1となります


入力例 2

1
21+

出力例 2

OK
11

29+に書き換えると、答えが最大になります


入力例 3

1
21-

出力例 3

OK
8

91-に書き換えると、答えが最大になります


入力例 4

0
1+1

出力例 4

NG

このような式は、逆ポーランド記法としては正しい式ではありません


入力例 5

3
1234567

出力例 5

OK
13

12+4+6+と書き換えると、答えが最大になります


Submit提出する