题目背景

z老师不在，小q打开了u2!#u_f9f**30&8.io。——一个跳方格的小游戏。 小q坐到了靠里的一排，认为不会被发现，但他身后是反光的玻璃窗。 这是一个致命的失误。

题目描述

现在z老师对这个游戏产生了兴趣，他准备尝试一下。 z老师有一个n * m的网格，每个格子上都写着一个数字。为方便描述，令左上角的网格为(1,1) ，右下角的网格为(n * m) 。 z老师可以进入最下方第 n行的任意一个网格，并按照以下规则进行游戏：

1.设z老师 第一次进入第i 行的位置为(i,j) ：

2.如果z老师在(i,ri) ，则他只能向左或向上跳。否则他可以向左，向右或向上跳。 z老师不能跳出网格，除非他在第1 行，这代表结束整场游戏。 定义一局游戏的得分为所有z老师经过的格子上的数字之和。z老师想求出得分的最小值。

输入格式

第一行两个整数n,m ，分别表示网格的行数和列数。 接下来n 行，每行 m 个整数ai,j ，表示(i,j) 上的数。

输出格式

一行一个整数，表示最小值。

样例 #1

样例输入 #1

5 4
-21589 7315 -8753 28191
21541 1236 2038 11098
4408 8833 3280 -28896
19889 21948 -1769 25387
22241 888 -6112 28106

样例输出 #1

-25590

提示

对于5%的数据，ai,j<=0 。 对于另外 10% 的数据，n,m<=5 。 对于另外 15% 的数据，n=2 。 对于另外 20% 的数据，n,m<=90 。 对于另外 20% 的数据，n,m<=400 。 对于全部数据 1<=n,m<=1000,-106<=ai,j<=106 。