Minimum Energy Path in a Grid

You are given a grid of size \(P \times Q\) where each cell has an associated energy cost. Starting from the top-left cell (1,1), you need to reach the bottom-right cell (P,Q) by only moving either to the right or downward. Your task is to compute the minimum total energy required to complete this journey.

Note: The energy cost of a path is the sum of the costs of all the cells visited along that path. Formally, if \(dp[i][j]\) represents the minimum energy required to reach cell \((i,j)\), then the recurrence relation is given by:

\[ dp[i][j] = \min(dp[i-1][j],\,dp[i][j-1]) + grid[i][j] \] for \(i,j > 1\), with appropriate initialization at the boundaries.

Your solution should read the grid from standard input and print the answer to standard output.

inputFormat

The first line contains two integers \(P\) and \(Q\), representing the number of rows and columns of the grid respectively. Each of the next \(P\) lines contains \(Q\) integers representing the energy cost of each cell in that row.

For example:

3 3
1 2 3
4 5 6
7 8 9

outputFormat

Output a single integer representing the minimum energy required to travel from the top-left corner to the bottom-right corner of the grid.

3 3
1 2 3
4 5 6
7 8 9

21