Maximum Straight Path Sum in a Grid

Given an r × c grid of non-negative integers, your task is to find the maximum sum of numbers along any single straight path, either along a row or a column. In other words, you need to compute the maximum among the sums of each row and the sums of each column.

More formally, let the grid be represented as \(A\) where \(A_{ij}\) represents the element in the \(i\)-th row and \(j\)-th column. You need to compute:

[ \max\left{ \max_{1 \le i \le r} \left( \sum_{j=1}^{c} A_{ij} \right), ; \max_{1 \le j \le c} \left( \sum_{i=1}^{r} A_{ij} \right) \right} ]

The answer should be output as a single integer.

inputFormat

The input is given via standard input (stdin) in the following format:

r c
A[1][1] A[1][2] ... A[1][c]
A[2][1] A[2][2] ... A[2][c]
... 
A[r][1] A[r][2] ... A[r][c]

Here, the first line contains two integers r and c, representing the number of rows and columns, respectively. Each of the following r lines contains c space-separated integers describing the grid.

outputFormat

The output should be printed on standard output (stdout) as a single integer representing the maximum sum of items along any row or column of the grid.

3 3
1 2 3
4 5 6
7 8 9

24