2165: 最小体力消耗

题目描述

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

输入描述

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

输出描述

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

提示

数据范围与提示

1≤m,n≤1000