問題
在这里,将用字符串表示生日蛋糕。蛋糕的每一部分用字符表示。每个字符的含义如下。
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
出力例 1
19
433 33 3通过分割该部分,可以获得效用 19 。
入力例 2
3 5 11111 1X1X1 11111
出力例 2
3
1 11通过分割该部分,可以获得效用 3 。