题目描述

有一张m×n个小方格的地图，每个小方格内有一个正整数。找出一条从左上角到右下角的路，使得沿途经过的所有小方格内的数之和最小。

注意：你只能向右或者向下走。

输入格式

第一行两个整数m(1≤m≤100)和n(1≤n≤100)，代表地图的行数和列数；

后面m行，每行n个正整数，代表小方格里面的数，中间有一个空格。

输出格式

一个整数，表示沿途经过的所有小方格内的数之和的最小值。

输入/输出样例

3 3
1 3 1
1 5 1
4 2 1

7

样例解释

沿途经过的小方格内的数是：1->3->1->1->1

说明/提示

时间1000ms，内存256MiB