A delivery rider has a map in the form of a grid. The number in each cell is the toll that the rider pays when he enters that cell. The rider starts at the top-left cell and must reach the bottom-right cell. He can only move right or down.
Return the smallest total toll he can pay (the first cell is counted too).
Examples
Example 1:
Input: grid = [[2,1,3],[4,8,2],[1,1,1]]
Output: 9
Explanation: One cheapest path is 2 -> 1 -> 3 -> 2 -> 1. Its total is 9.
Example 2:
Input: grid = [[5,3]]
Output: 8
Explanation: There is only one path: 5 + 3.
Example 3:
Input: grid = [[7,2],[3,9],[1,1]]
Output: 12
Explanation: The best path goes down all the way and then right: 7 + 3 + 1 + 1 = 12.