Участок на берегу

Миллионер Билл подал в мэрию прекрасного курортного города заявку на покупку участка на побережье. Администрация города согласилась выделить миллионеру участок, но выставила требование: в целях соблюдения принципов городского планирования участок обязательно должен быть прямоугольной формы и одна из его сторон должна быть параллельна гряде гор, идущих вдоль побережья.
Побережье представляет собой последовательность прямоугольных полос ширины один метр, одна из метровых сторон которых упирается в гряду гор, представляющую собой прямую линию. Полосы касаются друг друга боковыми сторонами. Море находится с противоположной от гор стороны полос (см. рисунок).
Помогите Биллу выбрать участок максимальной площади, удовлетворяющий требованиям мэрии.

PIC

Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат ввода
В первой строке входного файла записаны два числа:
n
— длина берега в метрах (
1
≤
n
≤
1
0
5
) и
t
— номер подзадачи. В следующей строке записаны через пробел
n
целых неотрицательных чисел
h
i
,
i
=
1
,
.
.
,
n
, не превосходящих
1
0
9
– последовательные длины всех полос в метрах. Номер подзадачи
t
определяет дополнительные ограничения на вид входных данных (см. описание системы оценивания ниже).
Формат вывода
В выходной файл требуется вывести единственное число — максимальную площадь участка.

0

Вы бы и рисунок прикрепили, который идет к условию

0