题目描述

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

输出格式
一个整数。

样例

3 3 
1 2 1

6

4 4 
3 2 4 2

17

5 6 
3 2 5 4 2 8

32