Two integer matrices and are given. You may perform the following operation at most once.
Let . Define the sum of the entries on or above the main diagonal of as
Find the maximum possible value of after performing the operation at most once.
The input is given in the following format:
For each case, print the maximum possible value of on one line.
Each case is given in the following format:
| 2 |
| 30 |
|
| 3 | 50 | No additional constraints. |