shapovalova12345

17.03.2020 21:44 •  Информатика

Ежедневные награды

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n

уровней. Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1

;

если игрок в предыдущий день зашёл в игру и получил награду уровня k
(k≠n), то за сегодняшнее посещение он получит награду уровня k+ 1

;

если игрок в предыдущий день зашёл в игру и получил награду уровня n
, то за сегодняшнее посещение он получит награду уровня 1

.

На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a1,a2, ...,an
золотых монет. Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m

дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные

Первая строка входных данных содержит натуральные числа n
и m (1 ≤n,m≤ 1000

) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n
целых чисел a1,a2, ...,an (1 ≤ai≤ 1000), где ai — величина награды i−

го уровня в золотых монетах.

Выходные данные

Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.

Примечание

В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7

золотых монет.

Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4
монеты, тогда в сумме он получит 8

монет.
Примеры
Ввод
3 3
4 2 1
Вывод
8

Ввод
3 3
1 2 4
Вывод
7