It's your birthday! For your Egyptian themed party, you decide to order a layered pyramid cake from one of Melbourne's famous hipster cafés. Following the hipster trend, this café packages cakes in an absurdly impractical but uniquely shaped box. The base of the box is a rectangular grid consisting of R rows and C columns, with rows numbered 1 to R from top to bottom and columns numbered 1 to C from left to right. However, the height of the box varies from cell to cell over the grid. To prevent the cake being squashed by the box, the number of layers at any point cannot exceed the height of the box at that point.
A pyramid cake consists of one or more rectangular layers, aligned with the sides of the box. Each layer has its top-left corner anchored at the top-left corner of the box--it must always cover cell (1, 1). To maintain structural integrity, each layer must rest completely on top of the one below, so that each cell covered by a particular layer is also covered by every layer underneath.
The volume of a layer cake is the sum of the number of cells covered by each layer. Wanting to eat as much delicious cake as possible, you would like to write a program to determine the maximum volume of a pyramid cake you can order. If no valid cakes fit inside the box, output 0.
R lines follow, each containing C integers. The jth number in the ith line, Hij, describes the maximum number of cake layers allowed at row i and column j of the grid.
4 4 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1
4 5 5 4 9 3 3 4 3 5 6 0 2 2 1 1 4 2 1 3 5 8
In the second sample case, we can order the cake described below.
Observe that the top-left cell is covered in each of these layers. This cake has volume 16 + 8 + 8 + 3 + 1 = 36 which is the maximum possible for this case.