时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H要办个签证，办证处是一座 \(M\) 层的大楼，每层楼都有 \(N\) 个办公室，编号为 \(1..N\)，每个办公室有一个签证员，签证需要让第 \(M\) 层的某个签证员盖章才有效。每个签证员都要满足下面三个条件之一才会给小H盖章：

　　1. 这个签证员在 1 楼，即小H可以从1楼的任意一个房间的签证员盖章开始。
　　2. 小H的签证已经给这个签证员的正楼下（房间号相同）的签证员盖过章了。
　　3. 小H的签证已经给这个签证员的相邻房间（房间号相差 1，楼层相同）的签证员盖过章了，当然盖过章的签证员不会重复盖章。

　　每个签证员盖章都要收取一定费用，这个费用不超过 \(10^9\)。找出费用最小的盖章路线，使签证生效。

【输入格式】

　　第 1 行两个整数 \(M\) 和 \(N\) 。
　　接下来 \(M\) 行每行 \(N\) 个整数，第 \(i\) 行第 \(j\) 个数表示第 \(i\) 层的第 \(j\) 个签证员收取的费用。

【输出格式】

　　输出最小的费用。

【输入输出样例】

　Input

3 4
10 10 1 10
2 2 2 10
1 10 10 10

　Output

8

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤M≤1000\)，\(0<N≤1000\)

【来源】

　　Mr.he