Given a rows x cols grid filled with non-negative numbers, write a program to find a path from top left to bottom right in which the sum of all numbers along its path is minimum.

Problem Note

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

Example 1

Input:
[   
  [1, 2, 8], 
  [4, 1, 5],  
  [1, 2, 3] 
] 
Output: 9 
Explanation: The path 1→2→1→2→3 minimizes the sum.

Example 2

Input:
[   
   [1, 3, 1],  
   [2, 9, 1],  
   [4, 2, 1] 
] 
Output: 7 
Explanation: The path 1→3→1→1→1 minimizes the sum.