The house in the olive grove. (olivetrees)

Vangelis has a field with olive trees. The field's shape is a rectangular, and we can imagine it as a grid of N rows and M columns. The olive trees are positioned along the columns, starting from the southern side of the field, and each one occupies a square of the grid, as shown in the following diagram. Some columns have more and others have fewer olive trees.

In our example there are ~N=6~ rows και ~M=7~ columns. The first column has ~4~ olive trees, the second one has ~5~, the third one has ~2~, the fourth one has ~1~, the fifth one has ~5~, and the sixth and seventh have ~3~ olive trees each.

Vangelis notices that there is plenty of space in the northern part of his field that is not planted with olive trees. Therefore, he decides to utilize it by building his house there. He wants to find the rectangle with the maximum possible area in which no olive tree is located. In our example, the largest house Vangelis can build is ~4 \times 2 = 8~ grid squares big and is shown in the following diagram in brown.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the dimensions of the olive grove and the number of olive trees in each column. The program should then print the maximum possible area of the house that Vangelis wants to build.

Input Files:

The input files with the name olivetrees.in are text files with the following structure: The first line consists of two space separated integers : the number of rows N and the number of columns Μ. The second line consists of exactly ~M~ integers ~T_i~ (~1 \le i \le M~), separated in pairs by a single space: the number of olive trees of the ~i~-th column, for all the columns in order from left to right.

Output Files:

The output files with the name olivetrees.out are text files with the following structure. They must contain exactly one line with a single integer number: the maximum possible area of the rectangle that does not contain any olive trees.

Constraints:

• 1 ~\le~ N ~\le~ 1.000.000
• 1 ~\le~ M ~\le~ 1.000.000
• 0 ~\le~ ~T_i~ ~\le~ N for each ~i~, where ~1 \le i \le M~
• The total area of the olive grove (calculated as ~N \times M~) will not exceed 2.000.000.000.

Examples of Input - Output Files:

1o

STDIN (olivetrees.in)

6 7
4 5 2 1 5 3 3

STDOUT (olivetrees.out)

8

2o

STDIN (olivetrees.in)

1000 4
0 0 0 0

STDOUT (olivetrees.out)

4000

Explanation of the examples:

The first example corresponds to the images shown in the previous pages. The largest rectangle not covered by olive trees is of size ~4 \times 2 = 8~ grid squares.

In the second example Vangelis has an olive grove witout any olive trees. Therefore, the largest rectangle he can find covers the entire olive grove and has an area ~1000 \times 4 = 4000~ grid squares.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: olivetrees *)

for PASCAL coders

/* USER: username
LANG: C
TASK: olivetrees */

for C coders

/* USER: username
LANG: C++
TASK: olivetrees */

for C++ coders

/* USER: username
LANG: Java
TASK: olivetrees */

for Java coders

# USER: username
# LANG: Python
# TASK: olivetrees

for Python coders