#P2030. The Secret Number

The Secret Number

描述
你的任务是从一个矩阵中找出隐藏的秘密数字,该矩阵的每个元素是一个数字(0'0'-9'9')或字母(A'A'-Z'Z)。图1展示了一个示例矩阵。

图1:矩阵

秘密数字和其他非秘密数字以十进制数字序列的形式编码在矩阵中。你只需要考虑满足以下条件的数字序列 D1D2DnD_1 D_2 \ldots D_nDk+1D_{k+1}1k<n1 \leq k < n)在矩阵中必须位于 DkD_k 的正右侧或正下方。你需要找到以这种方式编码的最大数字。

在图1的矩阵中,图2展示了四个编码数字:9088209088202314003723140037239000372390003799309930。可以看到,通常两个或多个编码数字可能共享一个公共子序列。在这种情况下,秘密数字是 2390003723900037,因为它是矩阵中所有编码数字中最大的。

图2:编码数字

相反,图3展示的序列应被排除:908A2908A2 包含字母;2314993023149930 的第五位数字位于第四位的上方;9003790037 的第三位数字位于第二位的右下方。

图3:无效序列

编写一个程序,从给定的矩阵中找出秘密数字。

输入

输入包含多个数据集,每个数据集表示一个矩阵。每个数据集的格式如下:

WW HH
C11C12C1WC_{11}C_{12} \ldots C_{1W}
C21C22C2WC_{21}C_{22} \ldots C_{2W}
\ldots
CH1CH2CHWC_{H1}C_{H2} \ldots C_{HW}

在数据集的第一行,给出两个正整数 WWHHWW 表示矩阵的宽度(列数),HH 表示矩阵的高度(行数)。W+HW + H 不超过 7070

接下来的 HH 行对应于矩阵的行(从上到下顺序)。第 ii 行包含 WW 个字符 Ci1Ci2CiWC_{i1}C_{i2} \ldots C_{iW}(从左到右顺序)。你可以假设矩阵中至少包含一个非零数字。

在最后一个数据集之后,一行中的两个 00 表示输入结束。

输出

对于每个数据集,输出秘密数字。前导零应被省略。

样例输入

7 4
9R2A993
0E314A0
8A900DE
820R037
6 7
JH03HE
ID7722
0DA1AH
30C9G5
99971A
CA7EAI
AHLBEM
20 2
A1234567891234CBDEGH
BDEDF908034265091499
0 0

样例输出

23900037
771971
12345908034265091499