题目描述
迷宫被分成 N 行 M 列的格子。从上往下看，行的编号是 1 至 N。从左往右看，列的编号是 1至 M。你现在位于第 1 行第 1 列格子，迷宫的出口在第 N 行第 M 列的格子。每进入一个格子都要消耗能量。迷宫格子的能量有点奇特，同一行格子消耗的能量是相等的，第 1 行的每一个格子消耗的能量都是 E[1]，第 2 行的每一个格子消耗的能量都是 E[2],....第 N 行的每一个格子消耗的能量都是 E[N]。现在你要从左上角格子走到右下角格子，每一步可以从当前格子走到相邻的上、下、左、右四个格子之一，你的目标是消耗最小的总能量。注意：左上角格子和右下角格子消耗的能量也要算。
输入
第一行，M 和 N。
接下来有 N 行，第 i 行是 E[i]。
输出
一个整数。
样例输入输出
提示
【数据范围】
1 <= N <= 50, 1 <= M <= 1000000000。注意：M 表示列，N 表示行。
1 <= E[i] <= 1000