迷宫被分成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
输入：
5 6
3 2 5 4 2 8
输出：
32
【数据范围】
1<= N<= 50， 1<= M<= 1000000000。注意：M表示列，N表示行。1<=E[i]<=1000。
4 4
3 2 4 2
17