2870: Note

数学课上，D 突然想到一件很重要的事情要告诉 Z，但是她们分别坐在教室的左前方和 右后方，这可怎么办呢？ D 决定传纸条！ 但是问题又出现了，D 要告知 Z 的是个机密，D 不希望有很多人知道。可是由于纸条 必须经过其它同学，所以 D 只好希望知道这个机密的人越少越好。 每个同学都有一个好奇程度 k（0≤k≤20） ，好奇程度越大，偷看纸条的可能性也就越 大，D 希望传递纸条的路径经过的同学的好奇程度和越小越好。 我们假定每个同学只会将纸条传递给 ta 后方或者右方的同学。

第 1 行，两个整数 n，m，表示教室有 n 行 m 列。 （1≤n，m≤100） 第 2 行到第 n+1 行，每行 m 个整数，表示每个同学的好奇程度。 其中 D 在第 1 行第 1 列，Z 在第 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

52