该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

新年到了，李老师的仓库已经有很多年没有清扫了，所以这次的计 划是用河水来冲。仓库是一个 N*M 的矩形，且每个格子里都堆满了尘 土。相邻的格子之间都有门，要想让水冲进去，就必须打开这些门。这 可不是一件容易的事情。因为有些格子里土堆得很高，因此打开门就很 费劲。推开一扇从 A 格子到 B 格子的门，需要的力度值为 B 房间里土 堆的高度。写一个程序计算至少需要花费多少力气，才能使所有的格子 都进水。

Format

Input

第一行为 N 和 M(N, M <= 40)，代表仓库的大小。

以后 N 行，每行 M 个整数（每个数不超过 100），分别表示每个格子里 土堆的厚度。

Output

你得到的结果。所有的格子必须都进水。水是从左上角的格子进去 的。

Samples

3 4
3 5 2 1
7 3 4 8
1 6 5 7

26