Maximum Efficiency Path

You are given an n × n grid where each cell contains a non-negative integer representing the efficiency at that cell. Your task is to find the maximum achievable efficiency when moving from the top-left corner to the bottom-right corner of the grid.

You are only allowed to move either right or down at any step. Formally, if you denote the efficiency of a cell at row i and column j by grid[i][j], and the maximum efficiency to reach that cell by dp[i][j], the recurrence is given in latex as:

$$dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + grid[i][j]$$

Note: The path always uses exactly 2n-1 cells. Thus, for a grid where all cells have value 1, the maximum efficiency will be 2n-1.

Your goal is to implement a solution that computes this maximum efficiency.

inputFormat

The input is read from stdin and consists of:

• An integer n denoting the size of the grid.
• n lines follow, each containing n space-separated integers representing the grid values.

outputFormat

Output the maximum possible efficiency (i.e., the sum of the values along the optimal path) to stdout.

3
1 2 3
4 5 6
7 8 9

29