Taco Maximum Path Sum

You are given a square grid of integers with size ( n ). Your task is to determine the maximum sum achievable when moving from the top-left corner to the bottom-right corner of the grid. At each cell, you can only move either to the right or downward. The optimal path sum is computed using the recurrence relation: [ dp[i][j] = \max(dp[i-1][j],;dp[i][j-1]) + grid[i][j] ] where ( dp[i][j] ) represents the maximum sum to reach cell ( (i, j) ). Read the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input begins with an integer ( n ) indicating the size of the grid. This is followed by ( n ) lines, each containing ( n ) space-separated integers that form the grid.

outputFormat

Output a single integer representing the maximum sum along a valid path from the top-left to the bottom-right corner of the grid.## sample

3
1 3 1
1 5 1
4 2 1

12