Description

Given a m × n grid filled with non-negative numbers, find a path from the top-left to the bottom-right which minimizes the sum of all numbers along its path.

You can only move either down or right at any point in time.

Input format:

• Line 1: JSON 2D array representing the grid

Examples

Input:
[[1,3,1],[1,5,1],[4,2,1]]

Output:
7

Input:
[[1,2,3],[4,5,6]]

Output:
12

Note:

Print a single integer — the minimum path sum.