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

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

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

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

;

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

;

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

.

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