D. 迷宫

题目描述

有一个$n \times m$的迷宫，每个格子有一个数字。你需要从左上角出发走到右下角，每次只能向右或者向下走，一条路径对应的字符串是经过点数字拼起来的串。求所有路径对应字符串最小字典序的串

输入格式

第一行输入两个整数$n, m$

接下来$n$行，每行$m$个数字，表示迷宫

输出格式

输出一个字符串表示结果

样例输入1

3 3
1 3 2
2 3 1
1 2 3

样例输出1

12123

数据范围

对于30%的数据，$n, m \leq 16$

对于60%的数据，$n, m \leq 100$

对于100%的数据，$n, m \leq 1000, 1 \leq a_{i,j} \leq 9$