题目描述

把一个区域分成n×m个小区域，设左上角为(1,1)，右下角为(n,m)。从(1,1)开始出发到(n,m)去，只能向右或向下走。

求一条路径使得路径上的所有的数字累加起来最大。输出这条路径由哪些数字组成。

输入格式

第一行两个整数n，m(1≤n, m≤10)，代表区域的行数和列数；

后面n行，每行m个不大于1000的，不重复的正整数，代表小方格里面的数，中间有一个空格。

输出格式

若干个整数，为最优路径的全部数字，按行走顺序输出。

输入/输出样例

4 4
1 3 5 9
2 6 11 7
8 10 12 0
4 13 14 15

1 2 8 10 13 14 15

说明/提示

时间1000ms，内存256MiB