Bager2

Inhabitants of neighbouring villages (call the villages A and B) cannot settle their border dispute. The disputed area is rectangular, composed of R×[] unit cells of land. Every cell has either some number of apple trees or some number of banana trees growing in it. A foreign counsellor has been asked to mediate in order to settle the dispute. He has decided that a bulldozer will pass through the area and destroy all trees in the cells it goes through. The bulldozer will start in the upper<left corner of the area and always move one cell down, right or diagonally down<right. The bulldozer stops when it reaches the lower<right corner. The village A will get the land below the bulldozer's path, while village B will get the land above it. Note that it is possible for one of the villages to receive no land at all. The counsellor noticed that people in village A prefer apples, while people in village B prefer bananas. So he decided to choose the bulldozer's path so that the sum of the numbers of apple trees below its path and banana trees above its path is the largest possible. Write a program that calculates this largest possible sum.