34. Программа стендапа

Стендап-комик Иннокентий составил программу из $N$ шуток. Каждую шутку он проверял, рассказывая её своей маме и засекая сколько секунд она смеётся. Недавно Иннокентий заметил, что его юмор настолько заразителен, что люди смеются над шуткой тем дольше, чем дальше она в программе. Более того, время, которое зал смеётся над каждой шуткой, можно посчитать как $(номер\ шутки) \times (время,\ которое\ над\ этой\ шуткой\ смеётся\ мама)$. К сожалению, комик уже не успевает перестроить всю программу. Однако он придумал новую шутку и хочет вставить её в программу так, чтобы зал смеялся над всей программой как можно дольше. Мама Иннокентия смеялась над новой шуткой $K$ секунд. Помогите комику понять, на сколько секунд дольше зал будет смеяться над всей программой, если он вставит новую шутку в идеальное место.

В первой строке входных данных находится одно число $K$ — количество секунд, которое мама комика смеялась над новой шуткой.

Во второй строке входных данных находится одно число $N$ — количество шуток в исходной программе.

В третьей строке находится $N$ целых чисел, разделённых пробелами. Каждое число $a_i$ — время, которое мама Иннокентия смеялась над i-й шуткой в программе.

Ограничения

Выведите одно целое число — количество секунд, которое добавится к времени смеха над всей программой, если вставить новую шутку в идеальное место.

Во втором примере над изначальной программой зал смеялся $1 \times 1 + 2 \times 4 + 3 \times 3 = 18$ секунд. Если добавить шутку, над которой мама комика смеялась $2$ секунды на второе место, то над новой программой зал будет смеяться $1 \times 1 + 2 \times2 + 3 \times 4 + 4 \times 3 = 29$. Таким образом, после добавления новой шутки зал будет смеяться над всей программой на $29-18=11$ секунд дольше.