Avoid The Snails

After the rain, Chris can finally walk back to his hostel. In order to do so, he must go through a park which can be seen as a matrix of size \(N\times M\). The entrance is on the bottom left and the exit is on the top right corner of the park. Chris wants to take the shortest path, so he will only move upward or to the right.

Unfortunately, the snails decided to come out for some fresh air! Each unit square has some number of snails on it. What is the minimum number of snails Chris will need to pass through?

Input File

Details and Assumptions:

  • The first line consists of two integers \(N\) and \(M\), denoting the number of rows and columns, respectively.
  • The next \(N\) lines contain \(M\) space separated integers. each number representing the number of snails in that square.
  • \(N = M = 1000\).
  • The number of snails in each square is at most 100.

Sample Input

3 3
1 2 2
3 4 5
1 2 4

Sample Output



Chris walks to the squares that has \(1\rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 2\) number of snails respectively.

Inspired by the number of snails I saw on my way back.


Problem Loading...

Note Loading...

Set Loading...