说明

迷宫被分成 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]。

输出格式

一个整数。

来源

历届试题