408045: GYM102966 I Integers Rectangle Challenge

Nlogonia casinos are very peculiar, instead of gambling, they challenge people to get the maximum "respect" points people can earn by solving some interesting mathematical problems. As the last contest of "El Gran Premio de México 2020" is running today, the casino decided to host a virtual challenge where the three contestants of a team have to work together to earn "respect" points, obviously, the more respect points the team wins, the better.

Once each of the three team members logs into the Nlogonia casino challenge platform (each using their own computer) each team member will be assigned a turn, $$$1$$$, $$$2$$$, or $$$3$$$, and each should push a button to notify they are ready to start. Once the three team members are ready the system will show a grid with $$$N$$$ rows and $$$M$$$ columns, each cell on the grid has a an integer number $$$R_{i,j}$$$, representing the amount of "respect" points the team can earn by selecting that cell, the same grid is shown to all team members. Then, the game begins. The team member with the turn $$$1$$$ has to select a rectangle from the grid, after selecting it, notifies the system and their turn is over. Next, the team member with the turn $$$2$$$ has to select another rectangle from the grid without overlapping with the rectangle selected by the team member with turn $$$1$$$, after selecting the rectangle, notifies the system and their turn is over. Last but not least, the team member with turn $$$3$$$, should select another rectangle from the grid that does not overlap with any of the rectangles selected by the other two team members, notifies the system, and then the game is over.

Once the game is over, the system will calculate the "respect" points earned by the team, this is a fairly simple calculation, the "respect" points the team will earn is the sum of the cells of the three selected rectangles. To show your skills in this challenge, you decided to write a program to find the maximum "respect" points your team can earn for a known grid from the casino system.

The first line of input contains two integer numbers separated by a space, $$$N$$$ and $$$M$$$ ($$$2 \leq N,M \leq 50$$$), representing the number of rows and columns in the grid shown by the system. Then $$$N$$$ lines follow, each of these $$$N$$$ lines contains $$$M$$$ integer numbers separated by a space, where the $$$j$$$-th number of the $$$i$$$-th line represents the value $$$R_{i,j}$$$ ($$$-1000 \leq R_{i,j} \leq 1000$$$), representing the "respect" points the team can earn if the cell at row $$$i$$$ and column $$$j$$$ is inside any of the selected rectangles during the game.

Output a line with a single integer number, the maximum "respect" points your team can earn with the given grid.

2 2
-2 -2
-2 -2

-6

4 4
1 1 1 1
-1 -1 -1 1
1 1 -1 -1
-1 -1 -1 -1

7

2 3
-1 0 -1
0 -2 -1

-1