C - 至高のケーキ
解説
/
今日もまた,きっと誰かの誕生日だ.ここでは,とあるイチゴが苦手な人の誕生日ケーキにまつわる次の問題に答えて欲しい.
ある人の誕生日ケーキを考える.誕生日ケーキは N 行 M 列から成り,N×M個の正方形に切り分けることができる.各正方形には「効用」が設定されており,ある人がその部分のケーキを食べた時どれだけ満足度を得られるか,が決まっている.彼が最終的に得られる満足度は,切り分けた正方形の効用の合計である.また,ケーキの一部はイチゴを含むことがある.
ここでは,誕生日ケーキを文字列で表すことにする.ケーキの各部分は文字で表す.ここで,各文字の意味は次のとおりである.
ケーキの効用といちごの場所が与えられるので,彼が得られる満足度の最大値を求めよ.
入力は以下の形式で標準入力から与えられる.
彼が得られる満足度の最大値を1行に出力せよ.
なお、最後には改行を出力せよ.
例えば,
このケースの場合,いちごがあるため,大きさ 3 以上のケーキは切り分けられない.よって,例えば
実行時間制限: 2 sec / メモリ制限: 64 MB
問題
ここでは,誕生日ケーキを文字列で表すことにする.ケーキの各部分は文字で表す.ここで,各文字の意味は次のとおりである.
0, 1, 2, ..., 9 : 書かれた数値の効用が得られる部分 X : イチゴを含む部分ここで,ある人に誕生日ケーキを切り分けることを考える.その人は階段上の形が好きなので,図 1 に示すような階段上の形のケーキを 1 つだけ切り分け,彼に与える.正方形 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
3 3 433 333 333
出力例 1
19
433 33 3という部分を切り分けることにより,効用 19 が得られる.
入力例 2
3 5 11111 1X1X1 11111
出力例 2
3
1 11という部分を切り分けることにより,効用 3 が得られる.