Maximum Sum Matrix :
Difficulty Level : Medium
Submissions : 250
Asked In :
Marks :10
: 6 | : 0
You are given a matrix of positive integers. You need to find the maximum possible sum of 2 integers from the matrix, such that the 2 integers are neither in the same row nor in the same column.
Input
The first line of input consists of two space separated integers, $$$n$$$ and $$$m$$$ $$$-$$$ which denote that the matrix has $$$n$$$ rows and $$$m$$$ columns. Then each of the next $$$n$$$ lines consist of $$$m$$$ space separated integers, where the $$$j_{th}$$$ number in the $$$i_{th}$$$ line denotes $$$a[i][j]$$$. $$$(1 \leq n*m \leq 10^6)$$$ $$$(1 \leq a[i][j] \leq 10^9)$$$
Output
The output should consist of a single integer - the maximum sum obtained.
Example
Input
2 2 5 19 4 13
Output
23
