Problem: Pyramid Cake

Want to try solving this problem? You can submit your code online if you log in or register.

Pyramid Cake

Input File: standard input
Output File: standard output
Time Limit: 5 seconds
Memory Limit: 256 MB

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.

Input

The first line of input will contain two integers R and C, describing the number of rows and columns in the box, respectively.

R lines follow, each containing C integers. The jth number in the ith line, H_ij, describes the maximum number of cake layers allowed at row i and column j of the grid.

Output

Your program must output a single integer: the maximum volume of a pyramid cake that fits inside the box. Since this number may be large, you may wish to use 64-bit integer types (such as long long in C/++) in your program.

Sample Input 1

Sample Input 2

Sample Output 1

Sample Output 2

Explanation

In the first sample case, you can order a cake with a single layer with its top-left at (1, 1) and its bottom-right at (3, 2). This gives you a total volume of 6, which is the maximum among all cakes you can order for this case.

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.

Subtasks & Constraints

For all subtasks, 1 ≤ R, C ≤ 1,000, and 0 ≤ H_ij ≤ 1,000,000 for all 1 ≤ i ≤ R and 1≤ j ≤ C.

For Subtask 1 (20 points), H_ij ≤ 1 for all i and j.
For Subtask 2 (25 points), H_ij ≤ 25 for all i and j.
For Subtask 3 (25 points), R, C ≤ 80.
For Subtask 4 (30 points), no further contraints apply.