As shown above, the image shows a square, and some of them have treasures. The number denotes the value of treasures.
A thief wants to get as many treasures as possible, in order not to be caught by police, he can only start from the square of the upper left corner , move rightwards and downwards without backing, to the square of lower right corner . Along the way on each trial, he can take away the treasure of the squares. Unfortunately, he only has two trials, that is, he will go from to twice. Notice that on the second chance, the treasures taken away on the first chance can't be taken again.
Given the size of the square, and the distribution of the values of treasures, find the maximum revenue the thief can get.
How to submit:
The pastebin below has inputs. Each input has the format:
A number , the size of the square.
numbers, the distribution of the values of treasures.
You should output: A number , the maximum revenue the thief can get.
Then submit the sum of all the outputs.