AT_wupc_03 至高のケーキ

[problemUrl]: https://atcoder.jp/contests/wupc2nd/tasks/wupc_03 今日もまた，きっと誰かの誕生日だ．ここでは，とあるイチゴが苦手な人の誕生日ケーキにまつわる次の問題に答えて欲しい． ある人の誕生日ケーキを考える．誕生日ケーキは $ 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行に出力せよ． なお、最後には改行を出力せよ． ```

3 3
433
333
333
```

 ```
19
```

 ```
3 5
11111
1X1X1
11111
```

 ```
3
```
                            

N/A

N/A