The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.

Given a two-dimensional array mat with values in it. Each value means the price we should pay for entering it. There is frog sitting in the top-left cell who wants to move to top-right. The frog can move to the nearest cell either right or down per one move. When it enters a cell, frog has to pay mat[i][j] for visiting it. Your goal is to find a path with minimal price. Return the cost of such a path.

Example 1

The orange path is minimum and costs 25.

Example 2

Input :

[[1, 3, 4],

[2, 1, 5],

[4, 6, 7]]

Output: 16

The path looks like:

Example 3

Input:

[[1, 2, 4],

[8, 5, 1]]

Output: 8

The Optimal Substructure here is to find the minimum path for each cell based on previous ones:

mat[i][j] = mat[i][j] + min(mat[i-1][j], mat[i][j-1])

This way, the minimum path to the mat[i][j] cell includes the price of this cell and the minimum price to one of the available cells (top or left).