C - 至高のケーキ Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

　今日もまた，きっと誰かの誕生日だ．ここでは，とあるイチゴが苦手な人の誕生日ケーキにまつわる次の問題に答えて欲しい．

問題

　ある人の誕生日ケーキを考える．誕生日ケーキは N 行 M 列から成り，N×M個の正方形に切り分けることができる．各正方形には「効用」が設定されており，ある人がその部分のケーキを食べた時どれだけ満足度を得られるか，が決まっている．彼が最終的に得られる満足度は，切り分けた正方形の効用の合計である．また，ケーキの一部はイチゴを含むことがある．

　ここでは，誕生日ケーキを文字列で表すことにする．ケーキの各部分は文字で表す．ここで，各文字の意味は次のとおりである．
 0, 1, 2, ..., 9 : 書かれた数値の効用が得られる部分
 X : イチゴを含む部分
　ここで，ある人に誕生日ケーキを切り分けることを考える．その人は階段上の形が好きなので，図 1 に示すような階段上の形のケーキを 1 つだけ切り分け，彼に与える．正方形 1 つの形も階段状であるとみなす．ただし，彼はいちごがとても苦手なので，いちごを含む部分は切り分けないようにしたい．例えば，図 2 のようにいちごを含むような切り分け方はできない．

　ケーキの効用といちごの場所が与えられるので，彼が得られる満足度の最大値を求めよ． 　
図1: ケーキの切り分け方
図2: 無効な切り分けの例
　 　 　

入力

入力は以下の形式で標準入力から与えられる． 
N　M
c_{1,1}c_{1,2} ... c_{1,M}
c_{2,1}c_{2,2} ... c_{2,M}
...
c_{N,1}c_{N,2} ... c_{N,M}
  • 1 行目にケーキの大きさを表す N(1 ≦ N ≦ 30) と M(1 ≦ M ≦ 30) が半角スペース区切りで与えられる．
  • 2 行目から N+1 行目には，M 文字の文字列が与えられる．これらケーキの効用値，あるいはいちごを表すデータである．
  • 文字列中に出現する文字列は '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'X' のいずれかであり，意味は上に記した通りである．
  • ケーキの文字列の中に出現する 'X' の数は N × M より少ないことを仮定してよい．

出力

彼が得られる満足度の最大値を1行に出力せよ．
なお、最後には改行を出力せよ．

入力例 1

3 3
433
333
333

出力例 1

19
例えば， 
433
33
3
という部分を切り分けることにより，効用 19 が得られる．

入力例 2

3 5
11111
1X1X1
11111

出力例 2

3
このケースの場合，いちごがあるため，大きさ 3 以上のケーキは切り分けられない．よって，例えば 
 1
11
という部分を切り分けることにより，効用 3 が得られる．