说明

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

输出格式

样例

5  6
3  2  5    4  2  8

32

提示