题目描述

数学课上，\(\text{Smart}\) 突然想到一件很重要的事情要告诉 \(\text{Sarah}\)，但是她们分别坐在教室的左前方和右后方，这可怎么办呢？

\(\text{Smart}\) 决定传纸条！

但是问题又出现了，\(\text{Smart}\) 要告知 \(\text{Sarah}\) 的是个机密，\(\text{Smart}\) 不希望有很多人知道。可是由于纸条必须经过其它同学，所以 \(\text{Smart}\) 只好希望知道这个机密的人越少越好。

每个同学都有一个好奇程度 \(k\)（\(0≤ k ≤20\)），好奇程度越大，偷看纸条的可能性也就越大，\(\text{Smart}\) 希望传递纸条的路径经过的同学的好奇程度和越小越好。

我们假定每个同学只会将纸条传递给他(她)后方或者右方的同学。

格式

输入格式

第一行两个整数 \(n,m\)，表示教室有 \(n\) 行 \(m\) 列。

第 \(2 \sim n+1\)行，每行 \(m\) 个整数，表示每个同学的好奇程度。

其中 \(\text{Smart}\) 在第 \(1\) 行第 \(1\) 列，\(\text{Sarah}\) 在第 \(n\) 行第 \(m\) 列，他们的好奇程度都为 \(0\)。

输出格式

输出一行包含一个整数，表示传递路径的好奇程度。

样例1

样例输入1

5 4
0 10 8 3
4 19 16 4
12 9 13 12
13 14 19 15
13 4 18 0

样例输出1

52

样例2

样例输入2

15 10
0 7 2 10 5 3 19 14 11 6 
7 8 4 8 10 0 9 4 5 17 
19 5 3 5 7 1 7 8 4 2 
16 1 13 19 14 16 3 9 8 11 
15 4 7 19 4 7 10 9 11 7 
15 9 14 11 9 6 18 11 13 15 
4 18 2 14 3 8 12 1 4 2 
5 5 2 4 3 15 15 7 12 12 
15 12 2 1 3 7 1 3 16 8 
16 11 9 7 8 1 2 14 3 2 
3 11 16 3 13 19 14 4 15 11 
5 13 3 1 3 12 6 17 12 4 
9 3 13 16 2 0 11 2 10 5 
16 14 4 19 13 5 14 17 12 11 
10 6 12 5 17 19 10 11 19 0 

样例输出2

108

样例3

样例输入3

10 26
0 10 12 2 10 3 11 17 17 6 8 2 4 5 1 6 11 5 4 9 4 5 11 1 18 17 
0 0 11 5 2 11 12 18 8 0 12 1 10 0 15 12 18 17 12 16 4 4 8 11 5 13 
0 2 0 7 9 2 11 13 15 0 5 1 16 1 0 4 13 19 16 18 6 5 0 4 10 1 
9 19 5 12 17 2 13 6 3 3 9 15 11 18 1 13 11 15 15 7 7 13 11 9 8 6 
17 0 1 13 13 4 13 6 0 5 17 5 5 7 9 5 19 13 14 2 5 4 3 1 17 7 
14 11 5 14 8 9 2 0 3 14 15 9 8 13 11 0 1 17 6 15 9 2 13 4 5 10 
15 12 17 12 18 15 12 15 6 7 4 18 5 8 2 18 3 3 9 17 8 1 12 10 7 0 
0 13 13 0 2 9 19 19 15 14 6 9 6 16 0 9 18 5 0 9 11 18 17 0 4 1 
13 6 19 1 16 8 13 14 18 13 13 3 1 3 6 13 17 2 7 14 18 17 3 14 16 19 
10 16 14 14 10 17 1 18 13 12 9 3 14 10 11 6 6 8 13 5 13 5 4 10 4 0 

样例输出3

170

限制

\(100\%\)的数据：\(1≤ n,m ≤100\)。