Shallowest Path Sum

Given a 2D depth map represented as a matrix, your task is to find the sum of depths along the shallowest path from the top-left corner to the bottom-right corner. You can only move right or down.

The problem can be formally stated as follows: Given a matrix \(A\) of dimensions \(n \times m\), find the minimum value of \(\sum_{(i,j) \in P} A_{i,j}\), where \(P\) is any path from \(A_{0,0}\) to \(A_{n-1,m-1}\) with moves only to the right or down.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 1000\)) representing the number of rows and columns in the matrix. The next \(n\) lines each contain \(m\) space-separated integers representing the depth values of the matrix.

outputFormat

Output a single integer, which is the sum of depths along the shallowest path from the top-left corner to the bottom-right corner.

1 1
5

5