E - 変な足し算

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

h、横 whw 個の正方形のマスに区切られたボードを考えます。各マスには0から91 桁の数字か、もしくは.(ドット)が書かれています。また、ボードには、左上のマスが (1, 1)、右上が (1, w)、左下が (h, 1)、右下が (h, w) となるように、それぞれのマスに対して順に座標が振られています。


ボード内に書かれた整数が 1 つになるまで以下の手順を繰り返します。

  1. 整数が書かれたマスの組で、マンハッタン距離が最大になるような組の中から 1 つをランダムに選びます。(マンハッタン距離とは、2 つのマスの座標がそれぞれ (a, b)(c, d) であるとき、|a - c| + |b - d| で計算される距離のことです)

  2. 1. で選んだ組において、マスに書かれた整数の和を元の数が大きいほうのマスに上書きし、小さいほうのマスには.を上書きします。もし元の数が等しい場合は、好きなほうに整数の和を上書きし、他方を.で上書きします。

上記手順が終了した後、ボード内に残る可能性のある整数のうち、最大のものを求めてください。


入力

入力は以下の形式で与えられる。

h w
b_1
...
b_h
  • 1 行目には、ボードの縦と横の長さを表す整数 h, w (1 \leq h, w \leq 100) が与えられる。
  • 続く h 行には、ボードの情報が与えられる。
  • b_i はボードの上から i 行目の情報を表し、0から91 桁の整数もしくは.を含む長さ w の文字列である。
  • ボードは少なくとも 1 つの整数を含むことが保証される。

出力

ボードに残る可能性のある整数のうち最大のものを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。


入力例1

2 3
12.
.5.

出力例1

8

入力例2

5 5
..3.9
.1..6
2.3.4
7..11
....8

出力例2

45