Time Limit: 2 seconds
Memory Limit: 32 Mb
You are an avant-garde architect renowned for your beautiful but highly unstable designs. Your current project is to build an apartment complex with striking profiles and gorgeous views.
Your apartment complex must consist of a number of floors, where each floor contains a number of apartments. It is extremely important that:
Some examples of valid and invalid buildings can be seen in the following diagram. Each of the buildings on the left hand side follows the rules above, and so is valid. All three buildings on the right hand side are invalid — in the first of these buildings the third floor contains two disconnected sections, in the second building the third floor does not rest upon the second, and in the final building the bottom floor does not touch the ground.
Unfortunately your creative desires are stifled by commercial constraints — your apartments will not sell unless they have the best possible views. For each point in space you have a number indicating how pretty the view is from that point. Your task is, given some number of apartments N, to design a building with precisely N apartments where the sum of these "prettiness numbers" for the N apartments is as large as possible.
For example, consider the grid on the left hand side of the diagram above. This gives the prettiness numbers for a strip of land, where the bottom row of numbers describe apartments on the bottom floor, the second row describes apartments on the second floor, and so on.
Suppose you are asked to create a building containing N = 10 apartments. An example of such a building is illustrated on the right hand side of the diagram. The sum of the prettiness numbers for this building is 8+9+6+5+6+7+6+7+5+6 = 65. With a little investigation it can be seen that this is the best possible building that you can create, i.e., no sum larger than 65 is possible.
Your program must read from standard input. The first line of input will contain the single integer N, the number of apartments that your building must contain.
The second line of input will be of the form W H, giving the dimensions of the grid of numbers. Following this will be H lines each with W space-separated integers, giving the prettiness numbers for the different points in space. The last row of input describes prettiness numbers for the ground floor, the second-last row describes the second floor, and so on. All prettiness numbers will be between 1 and 100,000 inclusive.
Your program must write a single line to standard output. This line must contain a single integer, giving the largest possible sum of prettiness numbers for your building.
10 7 6 9 3 6 4 8 1 3 2 9 2 5 3 2 6 1 1 8 4 6 5 4 1 9 6 5 3 4 5 6 2 5 6 7 1 2 2 6 7 5 6 4 3
The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.