Woburn Challenge 2015-16 Round 3 - Senior Division
While the dust settles in the battle between the dark knight and the last son of Krypton, the two have suddenly come to recognize the true mastermind behind it all. After General Zod's invasion on Earth, LexCorp was contracted by the U.S. government to carefully reverse-engineer leftover Kryptonian technology. As it turns out, the battle between the heroes had simply been Lex Luthor's test in his greater conspiracy to craft a powerful biotechnological weapon against Superman. At that point, it became clear to both that the world is in much graver danger than ever before. Now, the heroes have decided to team up and together, track down Luthor to end the evil mastermind's ploys once and for all.
They have tracked down Luthor's activities preceding their fight to Cadmus, a LexCorp subsidiary dedicated to genetic research on the outskirts of Metropolis. Unbeknownst to even the government, Cadmus has been conducting dangerous human experimentation for a secret biotechnology project. Infiltrating the facility, the heroes have discovered a huge number of human subjects that are held prisoner by Luthor. As they plan to secretly rescue all of them, Lex has already discovered their presence. Immediately, he sets his men, armed with advanced weaponry, into action to capture Batman and Superman. With a limited amount of time before they can escape, the duo must try to rescue as many prisoners as possible.
The Cadmus facility can be represented as a rectangular grid with rows of cells each , with the rows numbered from north to south, and the columns numbered from west to east. The -th cell in the -th row can be denoted as cell . Each cell happens to contain prisoners. Batman and Superman must work together to rescue as many as they can – but with the clock ticking, they have to make their rescue plan as efficient as possible.
Thus, Batman and Superman will each decide on their own "rescue zone". Each rescue zone is defined by a central point , a non-negative height , and a non-negative width . A rescue zone consists of cells - the central cell itself, the cells directly above it, and the cells directly to the left of it. This zone is only valid if all of its cells are within the grid - that is, and must hold true. However, to avoid getting in each other's way, their chosen rescue zones should not overlap with one another. In other words, no cell in the Cadmus facility may be part of both rescue zones. Following this, all prisoners in each cell which are either part of Batman or Superman's attack zones will be rescued.
Please write a program to help the Earth's greatest heroes determine the maximum number of prisoners that can be rescued this way.
Input Specification
The first line contains two space-separated integers and .
The next lines each contain integers, where line contains
integers , for .
Output Specification
Output a single integer, the maximum number of prisoners that can be rescued by Batman and Superman.
Sample Input
4 6
2 0 3 0 0 0
0 0 0 0 4 0
0 1 1 2 0 0
2 0 3 0 0 1
Sample Output
15
Explanation
One optimal pair of rescue zones is as follows:
- , , , (containing prisoners)
- , , , (containing prisoners)
Comments