LYC is the pet dog of Emperor Zhangzj of Yali Empire. Zhangzj has a huge affluence. Besides his palace, he has multiple estates. One of them is the Long Mansion, a famous site in Yali. LYC loves to play. One day, he accidentally enters the labyrinthine Long Mansion.
The mansion can be seen as a grid of **N** rows, indexed from **0** to (**N** - 1) from up to down, and **M** columns, indexed from **0** to (**M** - 1) from left to right. Initially, LYC is standing on the cell in the top left corner.
The exit is in the bottom right corner.
In other words, LYC wants to travel from row 0 and column 0 to row (N - 1) and column (**M** - 1).
LYC can walk from one cell directly to another if and only if they share a side.
He wants to reach the exit as soon as possible..
Unfortunately, each cell contains some obstacles that slow LYC down. For each cell we know the time LYC needs to spend there while passing through the cell. LYC also needs to spend that amount of time in the initial cell and in the exit cell as well. There is a pattern to the obstacles: each column of the mansion looks the same. In other words, all cells within any given row contain the same obstacle type, and therefore they delay LYC by the same amount of time. For example, the entire first row are some bushes, the entire second row contains some walls, and so on. You are given the times in the int[] **t**. More precisely, LYC will spend **t**[i] time in each cell he visits in row i.
You are given one int **M**, and one int[] **t**. Return the minimal time LYC needs to spend to reach the exit. |