最小体力消耗

题目描述

给定一个 $m×n$ 的迷宫，哪吒位于迷宫的左上角 $(1,1)$ 位置，白鼠妹妹躲在迷宫的右下角 $(m,n)$ 位置，每次哪吒只能向下或者向右移动一步，每一格有一个正整数 $k$，表示小灰鼠会咬掉哪吒 $k$ 的体力值，哪吒每走一格都会消耗k的体力值。若从左上走到右下，请计算哪吒消耗的最小体力，并输出路径。

输入格式

第一行是两个数字，分别是迷宫行数 $m$ 以及迷宫的列数 $n$，用空格隔开。 接下来是 $m$ 行，每一行有 $n$ 个数字，用空格隔开。

输出格式

第一行有一个数字，表示消耗的最小体力值。 第二行有 $m+n-1$ 个数字，用空格隔开，表示经过的路径。

3 3
1 3 1
2 5 4
4 6 1

10
1 3 1 4 1

提示

#### 数据范围与提示 $1≤m,n≤1000$

来源

童程童美