← 返回题目列表

AtCoder · wupc_03

C. 至尊蛋糕

中文机器翻译题面 查看原题
 今天也一定是某人的生日。在这里,请回答关于某个不喜欢草莓的人生日蛋糕的以下问题。

問題

 考虑某人的生日蛋糕。生日蛋糕是 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 。