小C 和 小L 是好朋友，他们总有聊不完的话题。一天他们坐在一间大小为 $R\times C$ 的课室里，小C坐在 $(1,1)$ 的座位上，小L坐在 $(R,C)$ 的座位上，其他座位都坐着同学。小C 想把一张纸条传给小L，只能向后和右两个方向传递；然而每个同学的八卦程度不同， $(i,j)$ 上的人的八卦程度为 $(a[i][j])$，小C想知道传递路径上八卦程度的值之和的最小值( $min(\sum a[i][j])$ )(（包括 小C 和 小L ）

输入格式

第一行为两个整数 $R$ , $C$ 表示教室共有 $R$ 行 $C$ 列

接下来的R行，每行有 $C$ 个整数，其中第i行j列的数表示 $(i,j)$ 上同学的八卦程度

输出格式

一个整数，为传递路径上八卦程度的值之和的最小值

样例

样例输入

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

样例输出

28

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65534\mathrm{KB}$

• 对于30%的数据 $R,C \le 50$ 。
• 对于60%的数据 $R，C \le 500$ 。
• 对于100%的数据 $R，C\le 2000 , 0\le a[i] [j] \le 10000$ 。